A constructive approach
The problem can be solved if the form of the solution is given.
Define the two factors using a hint (that these should be cubic equations) in the original post
y1 = x^3 - p1 x + q1
y2 = x^3 - p2 x + q2
Build a companion matrix of the polynomial $p(x)$
(This is a self-answer after discovering I can use Reduce directly.)
The previous answer gives ideas related to your approach of iterating palindromes.
Here, I present a way to directly compute them instead.
Directly computing $2,3$-palindromes
"...whether there is a way to do this computation faster?"
Rather than brute-force checking palindromes, you ...