I have solved this problem for $k=2$, but I tried for $k=3$ and I'm stuck.
To put this in a more specific context, I'll write briefly my solution for $k=2$.
Our goal is to find the positive integer solutions of the equation $2n(n+1)=m(m+1)$. Solving for $n$ yields $$m=\frac{-2+\sqrt{4+8n(n+1)}}4$$ so $1+2n(n+1)$ must be a square. But $1+2n(n+1)=n^2+(n+1)^2$, that is, $n$ is the lesser leg of a Pythagorean triple whose legs are consecutive integers. Some more work leads to a Pell equation, whose solution is related to the continued fraction of $\sqrt2$.
Well. Taking $x=2m+1$ and $y=2n+1$ we get $$ x^2 - k y^2 = 1-k. $$ We keep only solutions where both $x,y$ are odd, then we can take $m = (x-1)/2$ and $y=(y-1)/2.$ In all these, there is the solution $x=1, y=1.$ After that, the solutions come with a degree two linear recursion, such as the Fibonacci numbers obey. Oh, if $k$ is a square, there are only finitely many solutions, given by factoring. The simplest of these is $k=3,$ $$ x_{n+2} = 4 x_{n+1} - x_n, $$ $$ y_{n+2} = 4 y_{n+1} - y_n. $$ For $k=5,$ these relations (with multiplier $18$) apply to every third solution, for example $3571 = 18 \cdot 119 - 11.$ For $k=6,$ these relations (with multiplier $10$) apply to every other solution, for example $169 = 10 \cdot 17 - 1.$
We get more orbits as $k$ increases, although the growth is not steady, it depends more on the number of prime factors of $k-1$ than on simply the size of $k.$ Here is $k=13,$ note $2 \cdot 649 = 1298,$ while $1298 \cdot 2989 - 1 = 3879721.$ Also $1298 \cdot 32605 - 25 = 42321265.$