Solution:

Assume that $f_{k}(m)=f_{k}(n)=q$. Let us write the number $q$ in the form $q=a u^{2}$, where $a, u \in \mathbb{N}$ and $a$ is not divisible by any perfect square greater than 1. Since $m q=a m u^{2}$ is a perfect square, so is $a m$, and it follows that $m=a v^{2}$ for some $v \in \mathbb{N}$. Similarly, $n=a w^{2}$ for some $w \in \mathbb{N}$.
Since $f_{k}\left(a v^{2}\right)=a u^{2}$, $u$ is the smallest natural number greater than $v \sqrt{k}$. Analogously, $u$ is the smallest natural number greater than $w \sqrt{k}$, so it must hold that $|v \sqrt{k}-w \sqrt{k}|<1$. However, from this it follows that $|v-w|<\frac{1}{\sqrt{k}}<1$, so it must be that $v=w$, i.e. $m=n$.