The answer is $(2, 2)$ and $(2, 4)$.

For $n = 1$, we have $2 + 1 = 2$ which yields a contradiction.

If $n$ is a prime number, then $\phi(n) = n - 1$ and hence $2^n = n^m$. Therefore $m = n = 2$.

If $n = p^2$ where $p$ is a prime number, then $\phi(n) = p^2 - p$ and we get $2^{p^2} + (p-1)! = p^{2m} + 1$.
For $p > 2$ we have $(p-1)! \equiv 2 \pmod 4$ which is possible only when $p = 3$ but $2^9 + 2 = 514 = 3^{2m} + 1$ has no solution in integers. For $p = 2$, we get $m = 2$.

In all the other cases, let $p$ be the smallest prime factor of $n$. As $1 < p < 2p < \dots < p^2 < n$, we have $n - 1 - \phi(n) \ge p$ and therefore $p$ divides $(n - \phi(n) - 1)!$. Thus, $p|2^n - 1$ and $p$ is odd. As $p|2^{p-1} - 1$, $p|2^d - 1$ where $d = \gcd(n, p-1)$. Since $p$ is the smallest prime factor of $n$, we get $d = 1$ and hence $p|1$ which is a contradiction.