Prove: $f(x)^{p^k}\equiv f\left(x^{p^k}\right)\bmod p$

$p$ is a prime number, $k$ is an positive integer, and $f\in\Bbb Z[x]$.

Prove: $f(x)^{p^k}\equiv f\left(x^{p^k}\right)\bmod p$

Step One: Freshman's dream in characteristic $p$:

$$(a+b)^p\equiv a^p+b^p$$

Step Two: $n$-ary version (induct on $n$):

$$(a_1+\cdots+a_n)^p\equiv a_1^p+\cdots+a_n^p$$

Step Three: Polynomial version (little Fermat on coefficients):

$$f(x)^p\equiv (a_nx^n+\cdots+a_1x+a_0)^p\equiv\cdots\cdots \equiv f(x^p)$$

Step Four: Arbitrary power version (induct on $k$):

$$f(x)^{p^k}\equiv f(x^{p^k}).$$

This is false, unless you assume something about the function $f$ that you did not (assuming that it is a polynomial function with integer coefficients will do). As a simple counterexample, take $p=2$, $f(n)=\binom n2=\frac{n(n-1)}2$, $k=1$ and $x=3$, then $f(x)^p=3^2=9$ is odd while $f(x^p)=f(9)=36$ is even.

Since you assumed nothing at all about $f$, there are even simpler ways to get counterexamples. Take for $f$ the function that is $1$ at $x=3$ and $0$ everywhere else (in particular at $3^2=9$), again with $p=2$ and $k=1$.

Just in case an additional hypothesis on $f$ gets added to the question, I'll mention that the result is true for any function $f$ that is compatible with reduction modulo$~p$, in other words for which $x\equiv y\pmod p$ implies $f(x)\equiv f(y)\pmod p$. Then the result is simply a consequence of Fermat's little theorem which states that $a^p\equiv a\pmod p$ for all integers $a$. By iteration this implies $a^{p^k}\equiv a$ for all $a\in\Bbb Z$ and $k\in\Bbb N$, so that $$ f(x)^{p^k}\equiv f(x)\equiv f(x^{p^k}) \pmod p $$ where the second congruence uses the supposed compatibility of$~f$ with reduction modulo$~p$ (in other words both instances of the powering become no-ops modulo$~p$ and the identity becomes trivial). Polynomials with integer coefficients have the required compatibility with modular reduction, while polynomials with rational coefficients do not always, even if they map integers to integers always.

Added after the hypothesis $f\in\Bbb Z[x]$ was added to the question. Okay, so I misread the question, and made myself look rather stupid. Forgive me for reading $f(x)$ as a function being applied to an arbitrary value$~x$, which is what it would mean on most occasions; the main point I missed is that $x$ is an indeterminate here. I will remember this as a most striking example of what is so bad about writing polynomials as $P(x)$.

So the question really is about an identity in $\def\Zp{\Bbb Z/p\Bbb Z}(\Zp)[x]$, namely that raising any element to the power $p^k$ gives the same result as substituting $x^{p^k}$ for $x$. I would write this, using notation that I hope will be clear $$ Q^{p^k} = Q[x:=x^{p^k}] \qquad\text{for all $Q\in(\Zp)[x]$ and $k\in\Bbb N$.} $$ To prove it, note first that a substitution $Q\mapsto Q[x:=a]$ always defines a ring morphism, in the current case $a=x^{p^k}$ an endomorphism of $(\Zp)[x]$. So a first concern is that the operation $Q\mapsto Q^{p^k}$ on the left should also be a ring morphism. This is the case, because $r\mapsto r^p$ for $r\in R$ is an endomorphism in any ring$~R$ of characteristic$~p$ (the Frobenius endomorphism), and we are considering the $k$-th power of that endomorphism.

Now since we are comparing two endomorphisms of $(\Zp)[x]$, it will suffice to check that the result holds for $Q$ running through a generating set of $(\Zp)[x]$, one from which all other elements can be obtained by addition and multiplication. The set $\{1,x\}$ is such a generating set, and the identity above obviously holds for $Q=1$ and for $Q=x$. (I should warn that although the proof might suggest that the result holds if one replaces $(\Zp)[x]$ by another ring$~R$ (for instance a finite field) of characteristic$~p$, this is not so, since $\{1,x\}$ will no longer be a generating set; indeed the identity requires the Frobenius endomorphism to be the identity on$~R$, and this only holds for $R=\Zp$.)