c = Compile[{{k, _Integer}},
  Module[{out = {0}, start = 0, stop = 0, rlist = {0}, r = 0,
    sum = 0.0, diff = 0.0, imax = 8, step = 10},
   Do[
    If[j == k, imax = 2, imax = 8];
    Do[
     If[i == 2,
      start = i 10^j + 2;
      stop = (i + 1) 10^j - 1;
      step = 10;
      ,
      start = i 10^j;
      stop = (i + 1) 10^j - 1;
      step = 1;
      ];
     Do[
      rlist = IntegerDigits[n];
      r = 0;
      Do[
       r += rlist[[ri]] 10^(ri - 1)
       ,
       {ri, 1, Length[rlist]}
       ];
      If[r != n,
       sum = n + r;
       sum = Sqrt[sum];
       If[Floor[sum] == sum,
        diff = n - r;
        If[diff > 0,
         diff = Sqrt[diff];
         If[Floor[diff] == diff,
          AppendTo[out, n]
          ]
         ]
        ]
       ]
      ,
      {n, start, stop, step}
      ]
     ,
     {i, 2, imax, 2}
     ]
    ,
    {j, 0, k}
    ];
   out
   ]
  ];
Rest[c[9]] (*takes about 310 sec*)