Note that the "good states" to use in perturbation theory can't be eigenstates of $H_0+H'$, because if they were, we wouldn't have to do perturbation theory at all! The point of perturbation theory is to diagonalize $H_0+H'$, after all.
The "good states" to use in perturbation theory are those for which the off-diagonal elements of the matrix $\langle \psi_k^{(0)} | \hat{H}' |\psi_j^{(0)} \rangle$ vanish when $E_j=E_k$. This is because the second-order correction to the energy has the form
$$
E_n^{(2)} = \sum_{m\neq n}\frac{|\langle \psi_m^{(0)} | \hat{H}' |\psi_n^{(0)} \rangle|^2}{E_n-E_m}\,,
$$
and the only way to make sense of this when $E_n=E_m$ is if the top vanishes as well, so that we can neglect it in this sum and we don't therefore have to divide by zero. (Roughly speaking, of course; we can be more careful with how this works, but it's not necessary for this discussion.)
The way to enforce this condition is not to diagonalize $H_0+H'$ as a whole but only to diagonalize $H_0+H'$ when restricted to a degenerate subspace. That is, we take all the eigenstates $|\psi_m^{(0)}\rangle$ of $\hat{H}_0$ that correspond to the energy eigenvalue $E$, i.e.,
$$
\hat{H}_0|\psi_m^{(0)}\rangle = E|\psi_m^{(0)}\rangle\,,
$$
form the matrix of $\hat{H}'$ in this restricted subspace, and diagonalize just this matrix (which is not the full matrix of $\hat{H}'$!), yielding special linear combinations of the degenerate states $|\psi_m^{(0)}\rangle$ that will automatically satisfy our requirement. That is, since we've found the states that within the $E$-subspace that diagonalize this restricted matrix of $\hat{H}'$, the matrix elements in the first equation above are automatically zero, and so we don't run into this issue of dividing by zero in second-order perturbation theory.
There's a lot more to say: there are at least two more somewhat physical ways of understanding these states, one which involves taking advantage of symmetries of the system (or, equivalently, finding other operators that commute with our Hamiltonians that can be used to further label our states), and another which involves thinking about slowly "turning off" the perturbation and seeing what states are adiabatically connected at zero-perturbation. But the above discussion answers the question from a practical perspective.
