Design a set of $k$ primes $p_1 < p_2 < \cdots < p_k$ as follows. Begin by choosing $p_1 > 2m$. Having selected $p_j$, use Dirichlet's theorem to choose a prime
$$p_{j+1} \equiv -1 \pmod{p_1(p_1-1)p_2(p_2-1)\cdots p_j(p_j-1)}.$$
If $i < j$, then $p_i < p_j$, so $p_j$ does not divide $p_i - 1$; further, $p_j - 1 \equiv -2 \pmod{p_i(p_i - 1)}$, so $p_i$ does not divide $p_j - 1$.

Next, use the Chinese Remainder Theorem, to choose a positive integer $n$ such that $n \equiv -1 \pmod{p_1p_2\cdots p_k}$ and $n \equiv 0 \pmod{(p_1-1)\cdots(p_k-1)}$.

Finally, since $p_1p_2\cdots p_k$ and $m$ are coprime, and $(p_1-1)(p_2-1)\cdots(p_k-1)$ divides $n$, and $m$ is odd, Euler's Theorem applies to show that $m^n + n^m \equiv 1 + (-1)^m \equiv 0 \pmod{p_1p_2\cdots p_k}$. The conclusion follows.