Harry solved this problem:

I think that a condition is that $k$ is either odd or a multiple of 4. Here's why.

We need to be able to write $k=(y-x)(y+x)$ where $x$ and $y$ are integers. But $y-x$ and $y+x$ are either both even or both odd, so either their product is odd or it is a multiple of 4. So it is certainly necessary for $k$ to be odd or a multiple of 4.

It is also sufficient. If $k$ is odd, then $x=\frac{k-1}{2}$ and $y=\frac{k+1}{2}$ are integers, and $y^2-x^2=k$. If $k$ is a multiple of 4, then $x=\frac{k}{4}-1$ and $y=\frac{k}{4}+1$ are integers, and $y^2-x^2=k$.

Gabriel extended this further by noting that there are multiple solutions for various values of $k$

If $k$ is a multiple of $2n-1$ but not of $4n-2$, then

$$

x=\frac{k}{4n-2}-\frac{2n-1}{2}\quad\quad y=\frac{k}{4n-2}+\frac{2n-1}{2}

$$

If k is a multiple of $4n$, then

$$

x=\frac{k}{4n}-n \quad\quad y=\frac{k}{4n}+n

$$

So, for example, if $k=21=3\times 5\times 7$ then there are solutions

$$

(x, y ) = \left(\frac{105}{6}-\frac{3}{2}, \frac{105}{6}+\frac{3}{2}\right)\mbox{ or }\left(\frac{105}{10}-\frac{5}{2}, \frac{105}{10}+\frac{5}{2}\right)\mbox{ or }\left(\frac{105}{14}-\frac{7}{2}, \frac{105}{14}+\frac{7}{2}\right)

$$

We can see the patterns in these fractions. Simplifying gives us three solutions

$$

(x, y) = (16, 19), (8, 13), (4, 11)

$$

In this case, we can see how we might take the analysis further by writing $k$ as its prime factorisation

$$

(y-x)(x+y) = 3\times 5\times 7

$$

From this we can see, for example, $(x+y)$ is either $3,5,7,15,21$ or $105$.