In[409]:= PolynomialReduce[z^4 + z^2 + 4, z^2 - x, {z, x}][[2]] Out[409]= 4 + x + x^2 This is similar to the Solve approach in that both use algebraic means to effect the substitution. But one can be a bit more general using PolynomialReduce (by taking advantage of term orders, say).
For further detail on this approach, might have a look at some responses to these questions: