Make this an answer. It turns out that, using the recursion you describe, the set of all solutions to $x^2 - dy^2 = k$ split into a small number of orbits. The cleanest way to locate the "seed" values for the different orbits is Conway's topograph method. In essence, $k=\pm 1$ give the smallest number of orbits, namely one. Not much worse for $k $ prime. The number of orbits increases with the number of prime factors of $k,$ as long as the primes $p$ satisfy $(d|p)= 1.$ There is no truly easy way to find all the necessary seed values when $k$ is such a composite number.
Example: $11$ and $19$ are primes represented by $x^2 - 5 y^2,$ and $11 \cdot 19 = 209.$ The solutions to $x^2 - 5 y^2 = 209$ need more than one orbit under your recursion. We can make it worse by throwing in $29,$ and solving $x^2 - 5 y^2 = 6061.$ The only reason it is not bad is that we have class number one.
Here are the 8 seed pairs I get for $x^2 - 5 y^2 = 6061.$ If you apply the mapping
$$ (x,y) \mapsto (9x + 20y, 4x + 9y) $$
you get a pair with larger entries than any of these 8. A proof that these eight really are enough takes more work, although I have done plenty of these and think the list is complete.
x: 79 y: 6
x: 81 y: 10
x: 129 y: 46
x: 159 y: 62
x: 191 y: 78
x: 241 y: 102
x: 529 y: 234
x: 591 y: 262
Why not? Here is a longer list, including pairs from the same orbits:
x: 79 y: 6
x: 81 y: 10
x: 129 y: 46
x: 159 y: 62
x: 191 y: 78
x: 241 y: 102
x: 529 y: 234
x: 591 y: 262
x: 831 y: 370
x: 929 y: 414
x: 2081 y: 930
x: 2671 y: 1194
x: 3279 y: 1466
x: 4209 y: 1882
x: 9441 y: 4222
x: 10559 y: 4722
x: 14879 y: 6654
x: 16641 y: 7442
x: 37329 y: 16694
x: 47919 y: 21430
x: 58831 y: 26310
x: 75521 y: 33774
x: 169409 y: 75762
x: 189471 y: 84734
x: 266991 y: 119402
x: 298609 y: 133542
x: 669841 y: 299562
x: 859871 y: 384546
x: 1055679 y: 472114
x: 1355169 y: 606050
x: 3039921 y: 1359494
x: 3399919 y: 1520490
x: 4790959 y: 2142582
x: 5358321 y: 2396314
x: 12019809 y: 5375422
x: 15429759 y: 6900398
x: 18943391 y: 8471742
x: 24317521 y: 10875126
EDIT: it is possible to make a definition of "fundamental solution" that fits well into the group action on the form. As $x,y$ get large, we know that $y/x \approx 1/\sqrt 5 \approx 0.447213596.$ For large $x,y,$ we also know we can back up the solution by the inverse mapping,
$$ (x,y) \mapsto (9x-20y, -4x+9y) $$
and get another solution with positive $x,y.$ So, in a nod to Hurwitz, why not call a solution fundamental if either $9x-20y < 0$ or $-4x+9y < 0?$ That way, a solution is fundamental if either $y/x < 0.45$ or $y/x > 0.4444444.$ Below I list the first few solutions with the ratio $y/x$ in decimal. If that decimal is close to $0.44721$ then the solution is not fundamental. This can be upgraded to an "effective" set of bounds on $x,y$ to show that the set of fundamental solutions is finite. Good.
x: 79 y: 6 ratio: 0.0759494 fundamental
x: 81 y: 10 ratio: 0.123457 fundamental
x: 129 y: 46 ratio: 0.356589 fundamental
x: 159 y: 62 ratio: 0.389937 fundamental
x: 191 y: 78 ratio: 0.408377 fundamental
x: 241 y: 102 ratio: 0.423237 fundamental
x: 529 y: 234 ratio: 0.442344 fundamental
x: 591 y: 262 ratio: 0.443316 fundamental
x: 831 y: 370 ratio: 0.445247
x: 929 y: 414 ratio: 0.44564
x: 2081 y: 930 ratio: 0.446901
x: 2671 y: 1194 ratio: 0.447024
x: 3279 y: 1466 ratio: 0.447088
x: 4209 y: 1882 ratio: 0.447137
x: 9441 y: 4222 ratio: 0.447198
x: 10559 y: 4722 ratio: 0.447201
x: 14879 y: 6654 ratio: 0.447207
x: 16641 y: 7442 ratio: 0.447209
x: 37329 y: 16694 ratio: 0.447213
x: 47919 y: 21430 ratio: 0.447213
x: 58831 y: 26310 ratio: 0.447213
x: 75521 y: 33774 ratio: 0.447213
x: 169409 y: 75762 ratio: 0.447214
x: 189471 y: 84734 ratio: 0.447214
I did the same run for $x^2 - 5 y^2 = -6061.$ Here the ratio $y/x$ decreases until it gets lower than $0.45$
x: 8 y: 35 ratio: 4.375 fundamental
x: 28 y: 37 ratio: 1.32143 fundamental
x: 112 y: 61 ratio: 0.544643 fundamental
x: 128 y: 67 ratio: 0.523438 fundamental
x: 188 y: 91 ratio: 0.484043 fundamental
x: 212 y: 101 ratio: 0.476415 fundamental
x: 488 y: 221 ratio: 0.452869 fundamental
x: 628 y: 283 ratio: 0.450637 fundamental
x: 772 y: 347 ratio: 0.449482
x: 992 y: 445 ratio: 0.448589
x: 2228 y: 997 ratio: 0.447487
x: 2492 y: 1115 ratio: 0.447432
x: 3512 y: 1571 ratio: 0.447323
x: 3928 y: 1757 ratio: 0.447301
x: 8812 y: 3941 ratio: 0.447231
x: 11312 y: 5059 ratio: 0.447224
x: 13888 y: 6211 ratio: 0.447221
x: 17828 y: 7973 ratio: 0.447218
x: 39992 y: 17885 ratio: 0.447214
x: 44728 y: 20003 ratio: 0.447214
x: 63028 y: 28187 ratio: 0.447214
x: 70492 y: 31525 ratio: 0.447214
x: 158128 y: 70717 ratio: 0.447214
x: 202988 y: 90779 ratio: 0.447214