There appears to be much interest in the subject of the spectra of Cayley graphs. Indeed it appears that the spectra are highly related or may be computed through the irreducible representations of the underlying group in the graph, but I can not seem to a general formula for such a computation. For instance an old paper on the spectra of Cayley graphs http://www.sciencedirect.com/science/article/pii/0095895679900790 seems to compute the sum of eigenvalues.
In particular, I am interested in computing the largest and smallest eigenvalues of a particular Cayley graph of the symmetric group with a symmetric but not normal generating set. Is the above the only tool to do something like this? I am struggling to find anything more.
The sum of the eigenvalues of a (simple) graph is zero, so Babai's paper is not concerned with that.
The maximum eigenvalue of a regular graph is its valency so that is easy to compute.
For Cayley graphs of groups in general, I am not aware of any algorithm that is more efficient than the one presented by Babai.
Note that computing the least eigenvalue of a Cayley graph, given its connection set, is NP-hard even for Cayley graphs of abelian groups - deciding the maximum weight of a code word in binary linear code reduces to this. Also, even for normal Cayley graphs of symmetric groups, it is not easy to determine the least eigenvalue - we can compute the eigenvalue associated to a given partition, but there is no theory that predicts which partition belongs to the least eigenvalue.