The alternating group of degree 4 provides a model for counterexamples for all primes $p$ (and all powers $p^f$, not just $p^2$). Rather than viewing the alternating group acting on 4 unstructured points, think of it acting on the underlying set of a finite field. Rather than viewing it as all possible “even” permutations of the set, view it as all possible “affine” permutations of the set.
$\newcommand{\AGL}{\operatorname{AGL}} G=\AGL(1,K) = \{ f : K \to K : x \mapsto \alpha x + \beta ~\mid~ \alpha,\beta \in K, \alpha \neq 0 \}$
In the case of $A_4$, we take $K$ of order $4$. The subgroup $K_+ = \{ f : K \to K : x \mapsto x + \beta ~\mid~ \beta \in K \}$is a normal, elementary abelian, Sylow $p$-subgroup of $\AGL(1,K)$ whenever $K$ is a a finite field of characteristic $p$. The subgroup $K^\times = \{ f : K \to K : x \mapsto \alpha x ~\mid~ \alpha \in K, \alpha \neq 0\}$ is a cyclic subgroup of order $k_0=|K|-1$, relatively prime to the order of $K$.
If $K$ is chosen to be a field of size $p^2$, then $K_+$ is a normal, noncyclic Sylow $p$-subgroup of $G$ of order $p^2$, and $k$ divides $|G|=kp^2$, but of course $G$ has no subgroup of order $k_0p$, much less an element of order $k_0p$.
Proposition: The orders of elements of $G$ are exactly $\{p\} \cup \{ k : k \text{ divides } k_0 \}$.
Proof: Clearly $K_+$ has elements of order $p$, and the cyclic group $K^\times$ has elements of the other orders. If $g$ has order $kp$ for $k$ dividing $k_0$, then because $\gcd(k,p)=1$ we can write $1=uk+vp$, and so $g=g^1 = g^{(uk)} g^{(vp)}$ and $b=g^{(uk)}$ has order $p$ while $a=g^{(vp)}$ has order $k$. Hence we have an element $a$ of order $k$ commuting with an element $b$ of order $p$. All such elements $b$ lie in $K_+$. Write $a = (x\mapsto \alpha x + \beta)$ and $b=(x\mapsto x+\gamma)$. Then one product of $a$ and $b$ is $x\mapsto \alpha x + (\beta+\gamma)$ and the other is $x\mapsto \alpha x + (\beta+\alpha \gamma)$. For these two maps to be the same, they must act the same on $0 \in K$, and in particular $\beta+\gamma = \beta+\alpha\gamma$ so that $\alpha=1$ or $\gamma=0$. In the first case, this means $\alpha =1$ and $a \in K_+$ has order dividing both $p$ and $k_0$, so $k=1$. In the second case, this means $b$ is the identity, contradicting $g$ having order a multiple of $p$. $\square$