Assuming $n$ and $m$ are coprime and $m$ is factored, first compute $a=\text{fibonacci}(k) \mod \varphi(m)$. Computing linear recurrence modulo $n$ is possible, e.g. via matrix exponentiation.

Then your expression is equal to $n^a \mod m$ which is easy to compute working $\mod m$.

$\varphi$ is Euler totient function.

Assuming $n$ and $m$ are coprime and $m$ is factored, first compute $a=\text{fibonacci}(k) \mod \varphi(m)$. Computing linear recurrence efficiently modulo $n$ is possible, e.g. via matrix exponentiation.

Then your expression is equal to $n^a \mod m$ which is easy to compute efficiently working $\mod m$ and fast exponentiation.

$\varphi$ is Euler totient function.

If the factorization of $m$ is unknown and $k$ is sufficiently large, I suspect the problem is quite hard.