Then how do you find a linear operator M* of which $|\Psi\rangle$ is an eigenstate?
Assuming M is a "normal" operator (more on that below), we don't know anything about what $|\Psi \rangle$ is right now, so just solve the equation
$$M^* |\Psi \rangle = \lambda |\Psi \rangle$$
as usual. The fact that you can write $\Psi$ in terms of the eigenstates of M doesn't mean anything about $\Psi$, because the eigenstates of a normal operator form a basis for all vectors. So we could write any vector like that.
I put this in bold just because it is at the core of what I think you are missing. And it is also for that reason that there would be no reason for a relationship between $M$ and $M^*$.
On normal operators (edit): An operator is "normal" if has $[M, M^{\dagger}] = 0$. Just about every operator we use in QM is normal in this sense:
- Any Hermitian operator is normal
- Any unitary operator is normal
- Any diagonalizable operator is normal (in fact, normal $\iff$ diagonalizable)
It looks like you are talking about a normal operator since you have written what looks like a sum of basis vectors, in which case $M$ would be diagonalizable. But in case you weren't - there are occasional non-normal operators in QM, like the creation/annihilation operators. The answer I gave above would not apply to these. That being said, for non-normal operators, I don't think there is any useful relationship between their eigenstates ($\psi_i$) and an operator $M$ which has as an eigenstate some vector $\Psi$ which is in the span of their eigenstates of the $\psi_i$ (phew... what a mouthful). The relationship is just too fuzzy.