Suppose that $k$ is not a perfect square. Then for $n=1$ we get $\lfloor k \rfloor = x^2$ is a perfect square, meaning $k$ cannot be an integer. With $0<\{k\} := k - \lfloor k \rfloor < 1$ we have $y^2_n = \lfloor kn^2 \rfloor = \lfloor \{k\}n^2 + \lfloor k \rfloor n^2 \rfloor = \lfloor \{k\}n^2\rfloor + x^2n^2 = \lfloor \{k\}n^2\rfloor + z^2_n$. Since the fractional part is always less than $1$ there exists an $N \in \mathbb{N}$ with $\frac{1}{N+1} \leq \{k\} < \frac{1}{N}$. Let $m \in \mathbb{N}$ be such that $(m-1)^2 \leq N < m^2$. Thus $1 \leq N-2m+1 \leq 2N-m^2 < N \implies \frac {m^2} {N} \leq 2$. Thus $1 \leq \frac{m^2}{N+1}\leq \{k\}m^2 < \frac{m^2}{N} \leq 2 \implies \lfloor \{k\}m^2 \rfloor = 1$. Thus $y_m^2 - z_m^2 = 1 \implies z_m=xm = 0 \implies \lfloor k \rfloor = 0$, meaning $\{k\} = k \implies \frac{1}{N+1} \leq k < \frac{1}{N}$. Claim: For $N \in \mathbb{N}, N\neq 2$ we can find a square between $2N+2$ and $4N$. If $N<7$ one can check by hand. Let $N\geq 7$ and $s \in \mathbb{N}$ such that $s^2 \leq 4N < (s+1)^2$. Then $s^2 - (2N+2) \geq 2(N-s)-3 \geq 2(N-2\sqrt{N})-3 > 0$. If $N \neq 2$ then let $l \in \mathbb{N}$ be such that $2N+2 \leq l^2 \leq 4N$. Thus $2 \leq kl^2 < 4 \implies \lfloor kl^2 \rfloor \in \{2,3\}$, which is a contradiction. If $N = 2$ then we have $5<\frac{16}{3} \leq 4^2k\leq \frac{16}{2}=8$ which is also a contradiction.

Consider the sequence of non-negative integers $\left\{y_n\right\}$, satisfying $y_n^2 = \left \lfloor kn^2\right\rfloor$. Then, we have $y_{n+1} - y_n < \sqrt{k\left(n+1\right)^2 + 1} - \sqrt{kn^2} = \frac{2nk + k + 1}{\sqrt{k\left(n+1\right)^2 + 1} + \sqrt{kn^2}} = f\left(n\right)$. Likewise, $y_{n+1} - y_n > \frac{2nk + k - 1}{\sqrt{k\left(n+1\right)^2} + \sqrt{kn^2 + 1}} = g\left(n\right)$. However, observe that $\lim_{n\to+\infty} f\left(n\right) = \lim_{n\to+\infty}\frac{2k + \left(k+1\right)/n}{\sqrt{k\left(1 + 1/n\right)^2 + 1/n^2 } + \sqrt{k}}=\sqrt{k}$, and similarly, $\lim_{n\to+\infty} g\left(n\right) = \sqrt{k}$. It follows that $\lim_{n\to+\infty} \left(y_{n+1} - y_n\right) = \sqrt{k}$. Thus, $k$ is a perfect square.