Say we have a matrix $M$ and we know that $M = UMU^\dagger$ where $U$ is a unitary matrix and $^\dagger$ indicates the conjugate transpose. It is clear that $M = k I $ is a solution, where $I$ is the identity matrix and $k$ is some scalar.
My question is whether this is the only possible solution for $M$? If so, is there a proof for this? If not, can it be made true by adding extra restrictions (eg. if we make the restriction that $M$ is symmetric or that $U$ is orthogonal rather than unitary).
Note that we can rewrite your equation as $$ M = UMU^\dagger \implies MU = UM. $$
By the spectral theorem for normal matrices, there exists a unitary matrix $V$ such that $U = VDV^\dagger$, where $D$ is diagonal and unitary. $M$ will necessarily commute with $U$ if $M$ has the form $M = VD_MV^\dagger$, where $D_M$ is any diagonal matrix.
If the eigenvalues of $U$ are distinct, then these are the only matrices $M$ that satisfy $MU = UM$.