I am trying hard to think of the reasons why not, so I will try to prove, that we can actually state that $\psi = \phi$.
So now assume as you said, that:
$$
\operatorname H \psi_k = E_k \psi_k
$$
and
$$
\operatorname H \phi_{k+K} = E_{k+K} \psi_{k+K}
$$
So now, if we take the difference between the two and we assume that
$\operatorname H$ is the same in both cases,
$$
\operatorname H \left( psi_k - \phi_{k+K} \right)
=
E_k \psi_k - E_{k+K} \phi_{k+K}
=
E' \left( \psi_k - \phi_{k+K} \right)
$$
Where I assumed, that any linear combination of two eigenfunctions will
yield an eigenfunction. Now we can rearrange:
$$
\left(E_k - E'\right) \psi_k = \phi_{k+K} \left( E' - E_{k+K} \right)
$$
Now we can invoke the orthogonality condition, by taking an inner
product with $\psi_k$:
$$
E_k - E' = (E' - E_{k+K}) \left<\psi_k \right| \left. \phi_{k+K} \right>
$$
Now if the eigen functions are different, then it means, that $E_k =
E'$. If we take an inner product with $\phi_{k+K}$ instead, then we
similarly deduce that $E_{k+K} = E' \implies E_k = E_{k+K}$. Now we can
start thinking whether the equal eigenvalue condition means degeneracy,
or being the eigenvalues being the same.
Suppose the eigenvalues $\psi$ and $\phi$ are not the same, then they
must be degenerate. However, I can not think of a way make use of
$\operatorname T$ operator in order to get ride of the degeneracy
possibility between $\psi$ and $\phi$.
This did not answer your question, but maybe it will give you some thoughts.