There are a few problems in your problem statement and your own answer. For instance, the matrix $M^{-1}K$ is not Hermitian if $M$ and $K$ are to be interpreted as the usual mass matrix and spring stiffness matrix. Also, it is not clear to me what OP means. Taking OP's question literally, then the answer is no. Degenerate normal modes not always come in complex conjugation pairs in classical oscillators. A counter-example (essentially the example given by @V.Moretti) is a set of two independent oscillators with equal frequency.
Still, let me try to sum up what have been said and make them more precise.
To avoid mathematical non-sense, we should stick to the simplest case: a finite collection of mechanical oscillators coupled to each other through springs.
The equation of motion is given by
$$
M\ddot{q} = Kq.
$$
Here $q$ is the (generalized) coordinates, which is a real, $n$ dimensional column vector. $M$ is the $n\times n$ mass matrix, and $K$ is the standard, $n\times n$ spring stiffness matrix. Both $M$ and $K$ are real, symmetric, and positive-definite. The positive-definiteness is required by physics as both the kinetic and potential energy must be bounded from below. (Strictly speaking, semi-positive-definiteness is allowed. Here I assume the positive-definiteness to make my life a bit easier.)
As a side note, we see that the matrix $M^{-1}K$ is not symmetric since $M$ and $K$ don't commute in general.
Now we make a change of coordinates by defining the following:
$$
x = M^{1/2}q.
$$
The meaning of $M^{1/2}$ is the following: since $M$ is a real, symmetric, positive-definite matrix, it can be brought to the diagonal form: $M=V\Lambda_M V^t$.$V$ is a $n\times n$ real orthogonal matrix, and $\Lambda_M = diag(m_1, m_2, m_3,\cdots m_n)$ is a $n\times n$ diagonal matrix. In particular, $m_i>0$ for all $1\le i\le n$. Therefore, we can define a new matrix, $M^{1/2}$, as
$$
M^{1/2} = V\left(\begin{array}{cccc}
\sqrt{m_1} & 0 & \cdots & 0\\
0 & \sqrt{m_2} & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \sqrt{m_n}
\end{array}\right)V^t.
$$
It is easy to check that $M^{1/2}M^{1/2}=M$, and it is real, symmetric, and positive-definite by construction. Likewise, $M^{-1/2}$ can be defined, and it is a real, symmetric, and positive-definite matrix, and $M^{-1/2}M^{1/2}=1_n$.
The equation of motion can then be written in terms of the new coordinates:
$$
\ddot{x} = M^{-1/2}KM^{-1/2}x \equiv Hx.
$$
Here $H = M^{-1/2}KM^{-1/2}$. We see that $H$ is real and symmetric. More importantly, it is positive-definite.
The rest is then clear: since $H$ is a real, symmetric, and positive-definite matrix, it can be diagonalized by a real, orthogonal transformation. The eigenvalues of $H$ correspond to the natural frequencies squared of the system. Again, it is important to have a positive-definite $H$; otherwise, the natural frequencies could be imaginary, which is unphysical in our current model. Most importantly, we see clearly from the analysis that, there is generically no degeneracy in the system. And, if there is any degeneracy, we shouldn't expect them to be related by complex-conjugation.
Still, the classical oscillators system possesses time-reversal symmetry. Thus, it is expected that is $x(t)$ is a solution and then $x(-t)$ is a solution. This is related to the fact that, for each normal mode, there are two solutions, $e^{i\omega t}$ and $e^{-i\omega t}$ (or, if you like, $\cos(\omega t)$ and $\sin(\omega t)$). This can be seen for a single oscillator. But this is not to be confused with the degeneracy of normal modes.