How do I replace a variable in a polynomial?

The reason why the replacement doesn't work is that replacement rules are not mathematical replacements, but pure structural replacements. Therefore the replacement z^2->x just looks for occurrences of the pattern z^2 and replaces that with x. Now z^4 doesn't match that pattern.

Also note that rules operate on the internal form, which doesn't always match the displayed form. For example, one would expect a-2b /. 2b->c to result in a-c, but it actually results in a-2b again, because internally the expression reads Plus[a, Times[-2, b]] (you can see that by applying FullForm), while 2b is Times[2,b].

To do the replacement wanted, one has to use a method which is aware of the mathematics instead of just the structure. One possibility is

Solve[p==z^4+z^2+4 && x==z^2, {p}, {z}]

which means "Solve the equations given for p while eliminating z". The result then is

{{p->4+x+x^2}}

Note that the curly braces around z are mandatory because otherwise Mathematica interprets it as domain, resulting in an error message because z is of course no valid domain. Also note that the documentation page of Solve omits the possibility of giving a list of variables to eliminate as third argument (at least I didn't find it). However, you'll find it in a Mathematica tutorial on eliminating variables (but there they use the third argument without braces, which at least for me results in an error message, as written above).

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:

• Question on "smart" replacing in Mathematica
• How to reduce the number of independent variables in Mathematica

 z^4 + z^2 + 4 /. z^(a_Integer) -> x^(1/2 a)

yields

4 + x + x^2