We prove the assertion of the problem by using the mathematical induction on $k$.

If $k=1$ let $n=1$. Then, $n^n - m = 1 - m$ is divisible by $2$ since $m$ is odd. So the assertion holds.

Suppose the assertion holds when $k = t$, we will show that the assertion holds when $k = t + 1$.
From the induction hypothesis, it follows that there exists a positive integer $n_0$ for which
$$n_0^{n_0} \equiv m \pmod{2^t}.$$
Since $n_0^{n_0}$ is odd, $n_0$ is odd. If $n_0^{n_0} \equiv m \pmod{2^{t+1}}$ is satisfied, then this $n_0$ satisfies the assertion for the case of $k = t + 1$. If not, we have $n_0^{n_0} \equiv m + 2^t \pmod{2^{t+1}}$. Let us show that $n = n_0 + 2^t$ will satisfy the condition in this case.
This $n$ is then odd and hence $n$ and $2^{t+1}$ are relatively prime, and by Euler's Theorem we have $n^2 \equiv 1 \pmod{2^{t+1}}$. Consequently, we have
$$n^n = n^{n_0+2^t} \equiv n^{n_0} \cdot n^{2^t} \equiv n^{n_0} \pmod{2^{t+1}}.$$
The binomial expansion of $n^{n_0} = (n_0 + 2^t)^{n_0}$ gives us
$$n^{n_0} = \sum_{i=0}^{n_0} n_i \cdot 2^{it} n_0^{n_0-i}.$$
Since from the fact that $it \ge t+1$ if $i \ge 2$, it follows that $2^{it} \equiv 0 \pmod{2^{t+1}}$ and we get
$$\begin{aligned} n^{n_0} &\equiv n_0^{n_0} + n_0 C_1 \cdot 2^t n_0^{n_0-1} \equiv (m + 2^t) + 2^t n_0^{n_0} \pmod{2^{t+1}} \\ &\equiv m + 2^t (n_0^{n_0} + 1). \end{aligned}$$
Since $n_0^{n_0} + 1$ is an even number, we get from the above that
$$n^n \equiv n^{n_0} \equiv m + 2^t (n_0^{n_0} + 1) \equiv m \pmod{2^{t+1}},$$
which shows that this $n$ satisfies the condition for $k = t + 1$, and this completes the induction.