Following the remarks at the end of Khalid Bou-Rabee's answer,I think there will be counterexamples when $p$ is odd. Here's a general strategy to construct them, following pretty much what happens when $p =2$ in that answer. Assume now that $p$ is odd.
It is known that almost all $p$-groups have automorphism group a $p$-group (with an appropriate measure). Take a finite $p$-group $G$ of class $2$ such that $X = {\rm Aut}(G)$ is a $p$-group. Then $C_{G}(X)$ meets $Z(G)$ non-trivially. Let $z$ be an element of order $p$ in $C_{G}(X) \cap Z(P)$. Now $G$ contain a non-central element $s$ of order of order $p.$ Setting $A = C_{X}(s),$ we see that $\langle z,s \rangle \leq C_{G}(A),$ so that the latter group is not cyclic.