Solving the Pell equation $ x^2 - (k^2-1)y^2 = 1 $, the general solutions for $y$ are generated by the recurrence relation
$y_{n+2} = 2k\cdot y_{n+1} - y_n, y_0 = 0, y_1 = 1$
which is the same of the Chebyshev Polynomial of the Second Kind and so the $n$th-solution for $y$ is $y= U_{n}(k) $
Now if if we generalize the equation to $ x^2 - (k^2-1)y^2 = p $, with $p$ an odd prime, it's possible to say, using the Binary Quadratic Forms theory, that if the Legendre symbol $(\frac{k^2-1}{p}) = 1$ then one between $ x^2 - (k^2-1)y^2 = p $ and $(k^2-1)y^2 -x^2 = p $ has solutions (infinitely many), while the other have none.
Finding the first few solutions for $ k=2,3,4$ I noticed that this time the general solutions for $y$ are generated by the new recurrence relation
$y_{n} = 2k\cdot y_{n-2} - y_{n-4}$
Why this change happen? Is it still possible to use the Chebyshev Polynomials to find the $n$th-solution?
for your $k=4,$ try prime $p=7$ You are trying to represent either $7 = x^2 - 15 y^2$ or $-7 = x^2 - 15 y^2.$ Also, Legendre symbol $$ (15|7) = (1|7) = 1 $$
For $k = 2,3$ you really do get just one $\pm$ pair of genera and your idea works. For larger $k,$ there forms other than plus or minus the principal form, and represented primes not represented by $\pm$ the principal form