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, which as an example processes the same recurrence as in Theorem 6: $$F (n, f (n-1), f (n-2)) := f(n-1)(n2 + 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.