Solution:

First let us notice that for $m>n \geqslant 3$ we have $n^{m}>m^{n}$, so $\frac{n^{m}-m^{n}}{m+n}>0$. Indeed, the function $f(x)=\frac{\ln x}{x}$ is decreasing for $x>e$ since $f^{\prime}(x)=\frac{1-\ln x}{x^{2}}<0$, so $\frac{\ln n}{n}>\frac{\ln m}{m}$, i.e. $m \ln n>n \ln m$, and from there $n^{m}=e^{m \ln n}>e^{n \ln m}=m^{n}$.

For $n=2$ we may take $m=10$. Suppose that $n>2$. We have
$$n^{m}-m^{n} \equiv n^{m}-(-n)^{n}=n^{n}\left(n^{m-n}-(-1)^{n}\right) \quad(\bmod m+n)$$
We will look for $m$ in the form $m=k n^{n}-n\ (k \in \mathbb{N})$. Then $m+n=k n^{n} \mid n^{m}-m^{n}$ if and only if $k \mid n^{m-n}-(-1)^{n}$.

$(1^{\circ})$ If $n$ is odd, then $n^{m-n}-(-1)^{n}$ is even, so we can take $k=2$, i.e. $m=2 n^{n}-n$.

$(2^{\circ})$ If $n$ is even, then $n^{m-n}-(-1)^{n}=n^{m-n}-1$ is divisible by $n-1$, so we can take $k=n-1$, i.e. $m=(n-1) n^{n}-n$.