Note that $f_k(n+m) \equiv f_k(n) + f_k(m) \mod m$, and thus $f_k(n)$ is periodic in $n$ with (not necessarily minimal) period $m^2/\text{gcd}(m,f_k(m))$. Moreover, $f_{k+\phi(m)}(n) \equiv f_k(n) \mod m$ for sufficiently large $k$, $f_k(n) \mod m$ is eventually periodic in $k$ with period $\phi(m)$.
Therefore $f_k(k) \mod m$ is eventually periodic in $k$ with period $m^2 \phi(m)$.

EDIT: According to my calculations, the minimal periods of $f_k(k) \mod m$ for $m$ from $1$ to $20$ are

$$ \left[\matrix{ m &1&2&3&4&5&6&7&8&9&10&11&
12&13&14&15&16&17&18&19&20\cr \text{period}&1&4&18&8&100&36&294&16&
54&100&1210&72&2028&588&900&32&4624&108&6498&200} \right]
$$

This sequence does not seem to be in the OEIS.

Unsolved Problems in Number Theory(section A17). $\endgroup$ – Barry Cipra Mar 7 '13 at 22:01