There is such a solution if and only if both $k-1$ and $k+2$ have (well, different) integer expressions as some $u^2 + 3 v^2.$
The justification for that is in several answers I posted at
Find a solution: $3(x^2+y^2+z^2)=10(xy+yz+zx)$
$$ $$
$$ $$
Given
$$ p^2 + 3 q^2 = 2 + k, $$
$$ r^2 + 3 s^2 = 4(k-1), $$
we can solve
$$ (x^2 + y^2 + z^2) = k (yz + zx + xy) $$
with
$$ x = 2 p^2 + 6 q^2 - p r - 3 p s + 3 q r - 3 q s, $$
$$ y = 2 p^2 + 6 q^2 - p r + 3 p s - 3 q r - 3 q s, $$
$$ z = 2 p^2 + 6 q^2 + 2 p r + 6 q s. $$
I did not immediately realize, the process of Vieta Jumping lets us take a mixed solution and create one with all the same $\pm$ sign. Suppose
$x < 0,$ $y > 0,$ $z>0.$ We do a single jump:
$$ x \mapsto k(y+z) - x, $$
where the new $x$ value is then positive!
The permissible values of your $k$ from 2 to 1000 are
2 5 10 14 17 26 29 37 50 62
65 74 77 82 98 101 109 110 122 125
145 149 170 173 190 194 197 209 226 242
245 257 269 290 302 305 314 325 334 362
365 398 401 410 434 437 442 469 482 485
497 509 514 530 554 557 577 590 602 605
626 629 674 677 685 689 701 722 725 730
770 773 785 794 830 842 845 869 874 890
901 917 962 965 973 974 989
These all lead to solutions $(a,b,c) $ where it may be that some variables are negative, some positive.
Let me work up some of the smallest such $k,$ see whether positive solutions appear.
$$ k = 17; \; \; \; (377,17,5) $$
$$ k = 26; \; \; \; (418,13,3) $$
$$ k = 29; \; \; \; (1109,11,27) $$
BY RECIPE .........................................
Mon Jul 6 19:11:55 PDT 2020
2 ( 1, 1 , 4 ) p 1 q 1 r 1 s 1
5 ( -1, 5 , 17 ) ( 111, 5 , 17 ) p 2 q 1 r 2 s 2
10 ( 2, -1 , 5 ) ( 2, 71 , 5 ) p 0 q 2 r 3 s 3
14 ( -1, 2 , 11 ) ( 183, 2 , 11 ) p 2 q 2 r 2 s 4
17 ( -13, 23 , 47 ) ( 1203, 23 , 47 ) p 4 q 1 r 4 s 4
26 ( 3, -2 , 13 ) ( 3, 418 , 13 ) p 1 q 3 r 5 s 5
29 ( -7, 11 , 89 ) ( 2907, 11 , 89 ) p 2 q 3 r 2 s 6
37 ( -11, 19 , 31 ) ( 1861, 19 , 31 ) p 6 q 1 r 6 s 6
50 ( -5, 7 , 76 ) ( 4155, 7 , 76 ) p 2 q 4 r 2 s 8
62 ( -5, 7 , 22 ) ( 1803, 7 , 22 ) p 4 q 4 r 1 s 9
65 ( -61, 107 , 155 ) ( 17091, 107 , 155 ) p 8 q 1 r 8 s 8
74 ( 22, -17 , 109 ) ( 22, 9711 , 109 ) p 1 q 5 r 7 s 9
77 ( -13, 17 , 233 ) ( 19263, 17 , 233 ) p 2 q 5 r 2 s 10
82 ( 5, -4 , 41 ) ( 5, 3776 , 41 ) p 3 q 5 r 9 s 9
98 ( -4, 5 , 29 ) ( 3336, 5 , 29 ) p 5 q 5 r 5 s 11
101 ( -97, 173 , 233 ) ( 41103, 173 , 233 ) p 10 q 1 r 10 s 10
109 ( -29, 43 , 97 ) ( 15289, 43 , 97 ) p 6 q 5 r 0 s 12
110 ( -4, 5 , 83 ) ( 9684, 5 , 83 ) p 2 q 6 r 2 s 12
122 ( 6, -5 , 61 ) ( 6, 8179 , 61 ) p 4 q 6 r 11 s 11
125 ( -37, 59 , 105 ) ( 20537, 59 , 105 ) p 10 q 3 r 8 s 12
145 ( 7, -5 , 19 ) ( 7, 3775 , 19 ) p 0 q 7 r 12 s 12
149 ( -19, 23 , 449 ) ( 70347, 23 , 449 ) p 2 q 7 r 2 s 14
170 ( -15, 19 , 82 ) ( 17185, 19 , 82 ) p 5 q 7 r 1 s 15
173 ( -23, 31 , 97 ) ( 22167, 31 , 97 ) p 10 q 5 r 10 s 14
190 ( 5, -4 , 23 ) ( 5, 5324 , 23 ) p 0 q 8 r 9 s 15
194 ( -11, 13 , 292 ) ( 59181, 13 , 292 ) p 2 q 8 r 2 s 16
197 ( -61, 159 , 101 ) ( 51281, 159 , 101 ) p 14 q 1 r 4 s 16
209 ( -97, 119 , 611 ) ( 152667, 119 , 611 ) p 8 q 7 r 8 s 16
226 ( 8, -7 , 113 ) ( 8, 27353 , 113 ) p 6 q 8 r 15 s 15
242 ( 31, -24 , 115 ) ( 31, 35356 , 115 ) p 1 q 9 r 14 s 16
245 ( -25, 29 , 737 ) ( 187695, 29 , 737 ) p 2 q 9 r 2 s 18
257 ( 131, -109 , 755 ) ( 131, 227811 , 755 ) p 4 q 9 r 16 s 16
269 ( -79, 123 , 227 ) ( 94229, 123 , 227 ) p 14 q 5 r 10 s 18
290 ( 9, -8 , 145 ) ( 9, 44668 , 145 ) p 7 q 9 r 17 s 17
302 ( -7, 8 , 227 ) ( 70977, 8 , 227 ) p 2 q 10 r 2 s 20
305 ( -55, 69 , 293 ) ( 110465, 69 , 293 ) p 8 q 9 r 4 s 20
314 ( 43, -38 , 469 ) ( 43, 160806 , 469 ) p 4 q 10 r 13 s 19
325 ( -107, 199 , 235 ) ( 141157, 199 , 235 ) p 18 q 1 r 18 s 18
334 ( -11, 13 , 82 ) ( 31741, 13 , 82 ) p 6 q 10 r 3 s 21
362 ( 27, -23 , 178 ) ( 27, 74233 , 178 ) p 1 q 11 r 11 s 21
365 ( -31, 35 , 1097 ) ( 413211, 35 , 1097 ) p 2 q 11 r 2 s 22
398 ( -14, 19 , 55 ) ( 29466, 19 , 55 ) p 10 q 10 r 1 s 23
401 ( -79, 101 , 381 ) ( 193361, 101 , 381 ) p 16 q 7 r 20 s 20
410 ( -59, 67 , 610 ) ( 277629, 67 , 610 ) p 7 q 11 r 7 s 23
434 ( -17, 19 , 652 ) ( 291231, 19 , 652 ) p 2 q 12 r 2 s 24
437 ( -121, 179 , 381 ) ( 244841, 179 , 381 ) p 14 q 9 r 4 s 24
442 ( -34, 41 , 215 ) ( 113186, 41 , 215 ) p 9 q 11 r 6 s 24
469 ( -137, 211 , 397 ) ( 285289, 211 , 397 ) p 18 q 7 r 12 s 24
482 ( -4, 5 , 21 ) ( 12536, 5 , 21 ) p 11 q 11 r 7 s 25
485 ( -481, 905 , 1037 ) ( 942351, 905 , 1037 ) p 22 q 1 r 22 s 22
497 ( -313, 407 , 1403 ) ( 899883, 407 , 1403 ) p 16 q 9 r 16 s 24
509 ( -37, 41 , 1529 ) ( 799167, 41 , 1529 ) p 2 q 13 r 2 s 26
514 ( 44, -37 , 251 ) ( 44, 151667 , 251 ) p 3 q 13 r 18 s 24
530 ( 151, -125 , 772 ) ( 151, 489315 , 772 ) p 5 q 13 r 23 s 23
554 ( -29, 33 , 274 ) ( 170107, 33 , 274 ) p 7 q 13 r 5 s 27
557 ( -283, 347 , 1613 ) ( 1092003, 347 , 1613 ) p 14 q 11 r 14 s 26
577 ( -191, 361 , 409 ) ( 444481, 361 , 409 ) p 24 q 1 r 24 s 24
590 ( -10, 11 , 443 ) ( 267870, 11 , 443 ) p 2 q 14 r 2 s 28
602 ( 61, -50 , 291 ) ( 61, 211954 , 291 ) p 4 q 14 r 23 s 25
605 ( -81, 95 , 593 ) ( 416321, 95 , 593 ) p 10 q 13 r 8 s 28
626 ( 13, -12 , 313 ) ( 13, 204088 , 313 ) p 11 q 13 r 25 s 25
629 ( -511, 743 , 1661 ) ( 1512627, 743 , 1661 ) p 22 q 7 r 22 s 26
674 ( 133, -116 , 997 ) ( 133, 761736 , 997 ) p 1 q 15 r 13 s 29
677 ( -43, 47 , 2033 ) ( 1408203, 47 , 2033 ) p 2 q 15 r 2 s 30
685 ( -191, 283 , 595 ) ( 601621, 283 , 595 ) p 18 q 11 r 6 s 30
689 ( 101, -87 , 677 ) ( 101, 536129 , 677 ) p 4 q 15 r 20 s 28
701 ( -129, 161 , 671 ) ( 583361, 161 , 671 ) p 14 q 13 r 10 s 30
722 ( -140, 163 , 1063 ) ( 885312, 163 , 1063 ) p 7 q 15 r 1 s 31
725 ( -211, 323 , 615 ) ( 680261, 323 , 615 ) p 22 q 9 r 14 s 30
730 ( 14, -13 , 365 ) ( 14, 276683 , 365 ) p 12 q 14 r 27 s 27
770 ( -23, 25 , 1156 ) ( 909393, 25 , 1156 ) p 2 q 16 r 2 s 32
773 ( -71, 85 , 451 ) ( 414399, 85 , 451 ) p 10 q 15 r 4 s 32
785 ( -235, 653 , 369 ) ( 802505, 653 , 369 ) p 28 q 1 r 8 s 32
794 ( -47, 54 , 391 ) ( 353377, 54 , 391 ) p 11 q 15 r 10 s 32
830 ( -9, 10 , 103 ) ( 93799, 10 , 103 ) p 8 q 16 r 7 s 33
842 ( 15, -14 , 421 ) ( 15, 367126 , 421 ) p 13 q 15 r 29 s 29
845 ( -15, 19 , 73 ) ( 77755, 19 , 73 ) p 22 q 11 r 26 s 30
869 ( -49, 53 , 2609 ) ( 2313327, 53 , 2609 ) p 2 q 17 r 2 s 34
874 ( 41, -37 , 434 ) ( 41, 415187 , 434 ) p 3 q 17 r 15 s 33
890 ( 97, -89 , 1330 ) ( 97, 1270119 , 1330 ) p 5 q 17 r 17 s 33
901 ( 181, -149 , 871 ) ( 181, 948001 , 871 ) p 6 q 17 r 30 s 30
917 ( -859, 1415 , 2201 ) ( 3316731, 1415 , 2201 ) p 26 q 9 r 14 s 34
962 ( -65, 76 , 471 ) ( 526279, 76 , 471 ) p 14 q 16 r 13 s 35
965 ( 245, -223 , 2879 ) ( 245, 3014883 , 2879 ) p 10 q 17 r 28 s 32
973 ( -61, 155 , 101 ) ( 249149, 155 , 101 ) p 30 q 5 r 0 s 36
974 ( -13, 14 , 731 ) ( 725643, 14 , 731 ) p 2 q 18 r 2 s 36
989 ( -277, 411 , 857 ) ( 1254329, 411 , 857 ) p 22 q 13 r 8 s 36
Mon Jul 6 19:11:55 PDT 2020
Best Answer
October 14, 2015. This is with $$ \frac{x^2 + y^2}{xy - t} = q > 0, $$ which I believe to be the intent of the question.
THEOREM: $$ \color{red}{ q \leq (t+1)^2 + 1 } $$
I got some help from Gerry Myerson on MO to finish the thing. https://mathoverflow.net/questions/220834/optimal-bound-in-diophantine-representation-question/220844#220844
As far as rapid computer computations, for a fixed $t,$ we can demand $1 \leq x \leq 4 t.$ For each $x,$ we can then demand $1 \leq y \leq x$ along with the very helpful $x y \leq 4 t.$ Having found an integer quotient $q,$ we then keep only those solutions with $2x \leq qy$ and $2y \leq qx.$
In particular, for $t=1$ we find $q=5,$ then for $t=2$ we find $q=4,10.$ In both cases we have $q \leq (t+1)^2 + 1.$ We continue with $t \geq 3.$
With $t \geq 3, $ we also have $t^2 \geq 3t > 3t - 1.$
We are able to demand $xy \leq 4t$ by taking a Hurwitz Grundlösung, that is $2x \leq qy$ and $2y \leq qx.$ Define $k = xy - t \geq 1.$ Now, $xy \leq 4t,$ then $k = xy - t \leq 3t,$ then $k-1 \leq 3t - 1.$ Reverse, $3t-1 \geq k-1.$ Since $t^2 > 3t - 1,$ we reach $$ t^2 > k-1. $$
Next, $k \geq 1,$ so $(k-1) \geq 0.$ We therefore might get equality in $$ (k-1)t^2 \geq (k-1)^2, $$ but only when $k=1.$ $$ 0 \geq t^2 - k t^2 + k^2 - 2 k + 1, $$ $$ k t^2 + 2 k \geq t^2 + k^2 + 1. $$ Divide by $k,$ $$ t^2 + 2 \geq \frac{t^2}{k} + k + \frac{1}{k}. $$ Add $2t,$ $$ t^2 +2t + 2 \geq \frac{t^2}{k} + 2 t + k + \frac{1}{k}, $$ with equality only when $k=1.$ Reverse, $$ \frac{t^2}{k} + 2 t + k + \frac{1}{k} \leq t^2 +2t + 2 $$ with equality only when $k=1.$
Here is Gerry's best bit, this would not have occurred to me. Here we are back to considering all solutions $(x,y)$ and all $k=xy-t.$ Draw the graph of the quarter circle $x^2 + y^2 = k q.$ As $x,y \geq 1,$ there are boundary points at $(1, \sqrt{kq-1})$ and $( \sqrt{kq-1},1).$ The hyperbola $xy = \sqrt{kq-1}$ passes through both points, but in between stays within the quarter circle. It follows by convexity (or Lagrange multipliers again) that, along the circular arc, $$ \color{blue}{ xy \geq \sqrt{kq-1}}. $$ But, of course, $x^2 + y^2 = k q = qxy - t q$ is equivalent to our original equation $x^2 - q x y + y^2 = -tq.$ We have $$ -tq = x^2 - q x y + y^2 = (x^2 + y^2 ) - q x y = k q - q x y \leq kq - q \sqrt{kq-1}, $$ or $$ -tq \leq kq - q \sqrt{kq-1}, $$ $$ -t \leq k - \sqrt{kq-1}, $$ $$ \sqrt{kq-1} \leq t + k, $$ $$ kq -1 \leq t^2 + 2k t + k^2, $$ $$ kq \leq t^2 + 2 kt + k^2 + 1, $$ divide by $k,$ $$ q \leq \frac{t^2}{k} + 2 t + k + \frac{1}{k}. $$
For $t \geq 3$ and a solution with $xy < 4t,$ we showed $$ \frac{t^2}{k} + 2 t + k + \frac{1}{k} \leq t^2 +2t + 2 $$ with equality only when $k=1.$ For all solutions, Gerry showed $$ q \leq \frac{t^2}{k} + 2 t + k + \frac{1}{k}. $$ Put these together, we get $$ q \leq t^2 +2t + 2 $$ with equality only when $k=1,$ that is $xy = t+1.$
ADDENDUM, October 15. Here is another way to get Gerry's main observation, with $k = xy - t,$ that $xy \geq \sqrt{kq-1}.$ We have $x,y \geq 1$ and $kq =x^2 + y^2 .$ So $kq \geq x^2 + 1$ and $kq -(x^2 + 1) \geq 0.$ We also have $x^2 - 1 \geq 0.$ Multiply, $$ (x^2 - 1) kq - (x^4 - 1) \geq 0. $$ Next, $y^2 = kq - x^2,$ so $x^2 y^2 = kq x^2 - x^4.$ That is $$ x^2 y^2 = (kq-1) + (x^2 - 1)kq - (x^4 - 1). $$ However, $$ (x^2 - 1) kq - (x^4 - 1) \geq 0, $$ so $$ x^2 y^2 \geq kq - 1, $$ $$ \color{blue}{ xy \geq \sqrt{kq-1}}. $$