Very nice. I claim the answer are all odd $n>1$. Clearly $n\ne 1$, and let $n>1$ be an odd number. We take $p=2$ and $q$ such that $q\mid n^2+1$ and $q$ is prime. As $n^2+1\equiv 2\pmod{4}$ and $n^2+1>2$, such a $q$ indeed exists. With these choices, we take $m$ such that $m\equiv 0\pmod{q-2}$ and $m\equiv 2\pmod{q-1}$—such an $m$ exists by the CRT. By Fermat and the fact $q\mid n^2+1$, we get $n^m+1\equiv n^2+1\equiv 0\pmod{q}$, as desired. Now the proof. It suffices to verify $p=2$, which forces $n$ to be odd. Assume $2<p<q$. Let $d_1$ be the smallest positive integer such that $p\mid n^{d_1}-1$. Define $d_2$ similarly, i.e. $d_2>1$ and $q\mid n^{d_2}-1$. Notice $n^{p-1}\equiv 1\pmod{p}$ and $n^{q-1}\equiv 1\pmod{q}$. So, $d_1,d_2\nmid m$, $d_1,d_2\mid 2m$ and $d_1\mid p-1$ and $d_2\mid q-1$. Let $v_2(m)=k$. Then, $v_2(d_1)=v_2(d_2)=k+1$. So, $p,q\equiv 1\pmod{2^{k+1}}$. But then $p-q\equiv 0\pmod{2^{k+1}}$ and therefore $2^{k+1}\mid m$. This is a contradiction, so $p=2$.

For even $n$, here is a somewhat equivalent but prettier for me approach which the Hungarian students at MBL Balkans just figured out without paper! Since $n^m+1$ is odd, we must have $p,q$ to be odd, so $q-p$ and hence $m$ is even. This implies $(-1)$ is a quadratic residue mod $p$ and $q$, so $p,q \equiv 1 \pmod 4$ and so $4$ divides $q-p$ and hence $m$. So $x^4 \equiv -1$ has a solution mod $p$ and $q$ and so via orders or considering a primitive root we obtain $p,q \equiv 1 \pmod 8$. Continuing inductively, we obtain $p,q \equiv 1 \pmod {2^n}$ for all $n$, contradiction!

Well claim that the answer is all odd $n>1$. Clearly, $n=1$ fails. We first handle evens. By way of contradiction assume that there exists an even integer $n$ such that $q-p \mid m$ and $p,q\mid n^m+1$. If $2 \mid n$ then, $ 2 \nmid n^m+1$. But then, both $p$ and $q$ are odd primes, which implies that $q-p$ is even. Thus, $2\mid m$. Now, assume that we $\nu_2(n)=k$ for some positive integer $k$. Then, note that, \[n^m \equiv -1 \pmod{p} \implies n^{2m} \equiv 1 \pmod{p}\]Thus, $\text{ord}_p(n)\mid 2m$ but, $\text{ord}_p(n) \nmid m$. For all primes $p\neq 2$, $\nu_p(m) = \nu_p(2m)$ which implies that $\text{ord}_p(n)$ must be a power of two. Further, we must have that \[\nu_2(2m) \geq \nu_2(\text{ord}_p(n)) > \nu_2(m)\]which implies that $2^{k+1} \mid \text{ord}_p(n)$. But we also know that $\text{ord}_p(n) \mid p-1$ by Fermat's Little Theorem, which gives us that $2^{k+1} \mid p-1$. Thus, we conclude that $p \equiv 1 \pmod{2^{k+1}}$ and similarly, $q \equiv 1 \pmod{2^{k+1}}$. But then, putting this together with our previous condition, \[2^{k+1} \mid q-p \mid m\]which implies that $2^{k+1} \mid m$ which is a very clear contradiction. This means there indeed exists no solutions for even $n$ as claimed. Now, for odd $n$ we give the following construction. Let $p=2$. Let $q>2$ be a prime that divides $n^k+1$ for some positive integer $k$(clearly such primes exist since $n^k+1$ is not a power of two for all $k\geq 1$ by Mihailescu's Theorem). Then, note that $\text{ord}_q(n) \mid 2k$ but $\text{ord}_q(n)\nmid k$ which implies that $\text{ord}_p(n)$ must be even. Then, we let \[m=\frac{\text{ord}_q(n)}{2}(q-2)\]Now, clearly $q-2$ is odd. Thus, \[n^m+1 \equiv n^{\frac{\text{ord}_q(n)}{2}(q-2)}+1 \equiv n^{\frac{\text{ord}_q(n)}{2}} +1 \equiv -1 +1 \equiv 0 \pmod{q}\]Thus, $2,q\mid n^m+1$ and $q-2 \mid m$ by the nature of construction, as desired and we are done