By the Chinese Remainder Theorem, we can study the congruence modulo $p$, where $p$ is a prime dividing $m$. Therefore you can assume $k$ satisfies $ (n+k)^{n+k} \equiv n^n \pmod p $ for every $n \in \mathbb N$. In particular, $ (p+k)^{p+k} \equiv p^p \equiv 0 \pmod p, $ which leaves the only possibility $k \equiv 0 \pmod p$. Write $k = \ell p$. Then the conditions on $k$ becomes $ (n + \ell p)^{n + \ell p} \equiv n^{n + \ell p} \equiv n^n \pmod p $ if and only if, by Fermat's theorem, $ n^{\ell} \equiv n^{\ell p} \equiv 1 \pmod p. $ This implies $\ell \equiv 0 \pmod {p-1}$. Now suppose $k = p(p-1)m$, hence $ (n+p(p-1)m)^{n + p(p-1)m} \equiv n^{n+p(p-1)m} \equiv n^n \pmod p, $ so that $k$ satisfies the constraints. Therefore the $k$ that satisfy the desired properties are the multiples of $p(p-1)$ and the minimal one is clearly $p(p-1)$.
Going back to $m$, since we must have $m \equiv 0 \pmod {p(p-1)}$ for every prime $p$ dividing $m$, the minimal $k$ you are looking for is $ k = \underset{p | m}{\mathrm{LCM}} \{ p(p-1) \}. $
Hope that helps,