Squares in the Squares
MATL, 35 44.0 bytes
XK``x@2^tVKVXf1=a~]VKVnQ0h)UXKX^t1\

Try it online!
XK        % implicit input: n. Copy to clipboard K
`         % do...while. Each iteration applies the algorithm
  `       %   do...while. Each iteration tests a candidate number
    x     %     delete top of stack
    @2^   %     iteration index squared
    t     %     duplicate
    V     %     convert to string                
    K     %     paste from clipboard K: n or r_k
    V     %     convert to string  
    Xf    %     find one string within another. Gives indices of starting matches, if any 
    1=a~  %     test if some of those indices is 1. If not: next iteration
  ]       %   end. We finish with a perfect square that begins with digits of n or r_k
  V       %   convert to string
  K       %   paste from clipboard K: n or r_k
  VnQ0h   %   index of rightmost characters, as determined by r_k
  )       %   keep those figures only
  U       %   convert to number. This is the new r_k
  XK      %   copy to clipboard K, to be used as input to algorithm again, if needed
  X^      %   square root
  1\      %   fractional part. If not zero: apply algorithm again
          % implitic do...while loop end
          % implicit display