$(2, 2)$

Let $p = m^2 - mn + n^2 + 1$. First, we claim that $p$ is an odd prime number. Obviously, $p$ cannot be even, as $p$ divides the odd number $3^{m+n} + (m + n)!$, where $m + n \geq 2$. Suppose for the sake of contradiction that $p$ is composite. Then, $p$ has a prime factor $q$ with $q \leq \sqrt{p} \leq m + n$, which means $q$ divides $(m + n)!$. Since $q | p | 3^{m+n} + (m + n)!$, then $q | 3$, so $q = 3$. But that means $3$ divides $p = (2m - n)^2 + 1 - 3m(m - n)$; a contradiction since no integers of form $x^2 + 1$ is divisible by $3$. Hence, $p$ is prime. Now, by Fermat's little theorem, $3^{m^3 + n^3} \equiv \left( 3^{m^2 - mn + n^2} \right)^{m + n} \equiv 1 \pmod{p}$. Hence, $p = m^2 - mn + n^2 + 1$ divides $m + n + 1$. But then, $m^2 - mn + n^2 \leq m + n$, which is equivalent to $$ (m - 1)^2 + (n - 1)^2 + (m - n)^2 \leq 2 $$This reduces the possible solutions to $(1, 1)$, $(1, 2)$, $(2, 1)$, and $(2, 2)$. By checking again that $p$ must be odd, only $(2, 2)$ is possible, and finally for $m = n = 2$, $$ p = m^2 - mn + n^2 + 1 = 5 $$and it divides $3^{m+n} + (m + n)! = 3^4 + 4! = 105$ and $3^{m^3 + n^3} + (m + n) = 3^{16} + 4$.