This is just an extended comment.
There is no need to invoke the algebraic dependency search. The recurrence can be found by directly constructing Groebner basis $B$ under any term order, in which $n$ has the highest weight and $y_m$ corresponding to $f$ with largest index has the second highest weight. Then in $B$ we are interested in polynomials with degree of $n$ equal 0 and degree of $y_m$ equal 1.
Here is a sample Sage code (updated 2024-08-06), which as an example processes the same recurrence as in Theorem 6: $$F (n, f (n-1), f (n-2)) := f(n-1)(n^2 + n + 2) + f (n-2)(3n + 5).$$
It finds 3 independent solutions of the minimal possible order 4: $$f(n) = \tfrac{-16 f(n-3) f(n-1)^{3} + 24 f(n-4) f(n-1)^{3} + 56 f(n-3) f(n-2) f(n-1)^{2} - 84 f(n-4) f(n-2) f(n-1)^{2} - 366 f(n-4) f(n-3) f(n-1)^{2} + 189 f(n-4)^{2} f(n-1)^{2} - 24 f(n-2)^{3} f(n-1) + 444 f(n-3) f(n-2)^{2} f(n-1) + 174 f(n-4) f(n-2)^{2} f(n-1) - 164 f(n-3)^{2} f(n-2) f(n-1) - 1342 f(n-4) f(n-3) f(n-2) f(n-1) + 822 f(n-4)^{2} f(n-2) f(n-1) + 1092 f(n-3)^{3} f(n-1) + 312 f(n-4) f(n-3)^{2} f(n-1) - 567 f(n-4)^{2} f(n-3) f(n-1) - 252 f(n-2)^{4} + 230 f(n-3) f(n-2)^{3} + 341 f(n-4) f(n-2)^{3} - 2004 f(n-3)^{2} f(n-2)^{2} + 2348 f(n-4) f(n-3) f(n-2)^{2} - 2338 f(n-4)^{2} f(n-2)^{2} - 4954 f(n-3)^{3} f(n-2) + 12017 f(n-4) f(n-3)^{2} f(n-2) - 3672 f(n-4)^{2} f(n-3) f(n-2) - 7888 f(n-3)^{4} + 3672 f(n-4) f(n-3)^{3}}{24 f(n-4) f(n-2) f(n-1) - 16 f(n-2)^{3} - 4 f(n-4) f(n-2)^{2} - 27 f(n-4)^{2} f(n-2) - 54 f(n-3)^{3} + 27 f(n-4) f(n-3)^{2}},$$ $$f(n) = \tfrac{24 f(n-3) f(n-2) f(n-1)^{2} - 12 f(n-4) f(n-2) f(n-1)^{2} - 186 f(n-4) f(n-3) f(n-1)^{2} + 123 f(n-4)^{2} f(n-1)^{2} - 16 f(n-2)^{3} f(n-1) + 116 f(n-3) f(n-2)^{2} f(n-1) + 34 f(n-4) f(n-2)^{2} f(n-1) - 52 f(n-3)^{2} f(n-2) f(n-1) - 322 f(n-4) f(n-3) f(n-2) f(n-1) + 122 f(n-4)^{2} f(n-2) f(n-1) - 36 f(n-3)^{3} f(n-1) + 600 f(n-4) f(n-3)^{2} f(n-1) - 369 f(n-4)^{2} f(n-3) f(n-1) - 36 f(n-2)^{4} + 90 f(n-3) f(n-2)^{3} + 3 f(n-4) f(n-2)^{3} - 300 f(n-3)^{2} f(n-2)^{2} + 324 f(n-4) f(n-3) f(n-2)^{2} - 78 f(n-4)^{2} f(n-2)^{2} - 1238 f(n-3)^{3} f(n-2) + 2055 f(n-4) f(n-3)^{2} f(n-2) - 648 f(n-4)^{2} f(n-3) f(n-2) - 1392 f(n-3)^{4} + 648 f(n-4) f(n-3)^{3}}{8 f(n-3)^{2} f(n-1) - 12 f(n-4) f(n-2)^{2} + 51 f(n-4)^{2} f(n-2) - 58 f(n-3)^{3} - 51 f(n-4) f(n-3)^{2}},$$ $$f(n) = \tfrac{4 f(n-3) f(n-1)^{2} - 3 f(n-4) f(n-1)^{2} - 2 f(n-2)^{2} f(n-1) + 10 f(n-3) f(n-2) f(n-1) - 2 f(n-4) f(n-2) f(n-1) - 14 f(n-3)^{2} f(n-1) + 9 f(n-4) f(n-3) f(n-1) - 3 f(n-2)^{3} + 16 f(n-3) f(n-2)^{2} - 18 f(n-4) f(n-2)^{2} + 9 f(n-3)^{2} f(n-2)}{2 f(n-3) f(n-2) - 3 f(n-4) f(n-2) + 3 f(n-3)^{2}},$$ the last of which matches the one given in the paper.
ADDED. Since there is an interest in a faster code avoiding computation of Groebner bases, here is another Sage codeanother Sage code, which treats each term $n^uy_m^v$ as a variable and uses linear algebra to nullify the coefficients of such terms, except for $(u,v)=(0,0)$ and $(u,v)=(0,1)$. In general, it does not guarantee to produce solutions of the smallest possible order, but in turn it works much faster than the first code. For the recurrence quoted above, it happens to also produce a solution of the minimal order 4.