Does Eigenvalues evaluate in a parallelized way?

Eigenvalues (and some other builtin functions) may internally use a very efficient multithreaded implementation (depending on what sort of matrix it's applied to, i.e. sparse or dense, exact or inexact, etc.)

It is important to understand that this does not use Mathematica's parallelization framework and it is not user-controllable, apart from setting how many threads to use. You can read more about this here.

How many threads to use by these functions is controlled by the "MKLThreads" system option:

SystemOptions["MKLThreads"]

Update: In recent versions of Mathematica the option is SystemOptions["ParallelOptions" -> "MKLThreadNumber"].

This is set to the number of cores of your CPU on the main kernel, however, it is set to 1 on all subkernels. This explains the CPU usage patterns you see. 800% means that the process is using 8 cores.

Generally, when using a function that is already internally multithreaded, manual Parallelizeation will either not do anything or will slow things down.

I don't think you are Parallelize-ing the Eigenvalues. What your code is doing is generating 4 5000X5000 random Hermitian matrix and find the eigenvalues. You can check with a smaller order (say 5X5), like

m = # + ConjugateTranspose[#] &[Table[RandomReal[], {i, 5}, {j, 5}]];
ParallelDo[Eigenvalues[m];, {4}] // AbsoluteTiming
Do[Eigenvalues[m];, {4}] // AbsoluteTiming
Table[Eigenvalues[m], {4}] // TableForm

I define the matrix in m to make sure ParallelDo and Do are using the same matrix. For my laptop execution time for ParallelDo and Do are 0.011845 and 0.000189 (Do wins again). Last Table command will show you what exactly is happening. You can check each loop produce a complete set of eigenvalues. It is not like all the loops together produce the complete set.

Now regarding your query - why the parallelization takes more time than series execution - well, I don't know that well. Only thing I can say it is the effect of interdependence of kernels which sometimes also depends on how you set your loops. From my experience I would suggest that it is always good to do a test drive with both series and parallel to see what suits better with your code.