This problem is a lot of fun! There is a way you can reduce the general problem to studying average-integral polynomials (take an average-integral sequence, pick a finite but large enough subsequence, interpolate using an m-times-average-integral polynomial and then use your result on polynomials to conclude that the p-th power sequence is m-times average-integral), which, at the very least, helps shed some light on the general picture.
If I'm not mistaken the polynomials $a_nx^n+\cdots+a_0$ in $\mathbb Z[x]$ which are average-integral for $p=2$ are the ones for which $$\nu_2(a_k)\geq k-\nu_2(k!)$$ holds for all $k$. Similarly for $p=3$ we have the analogous conditions $$\nu_3(a_k)\geq \lfloor\frac{k}{2}\rfloor-\nu_3(k!).$$
Now something special happens in the cases $p\in \{2,3\}$, that such polynomials are closed under taking $p$th powers (essentially $\lfloor \sum \cdot\rfloor-\sum\lfloor\cdot\rfloor$ can not be large enough to construct a counterexample). But already for $p=5$ you have $1,n^2,n^7,n^{15}$ are all average-integral sequences, therefore so is their sum. But the following sequence $$a_n=(1+n^2+n^7+n^{15})^5$$ is not average-integral, giving us a counterexample.
Edit: Zeb in the comments gave the following counterexample for general $p>3$ $$(1+n^{p+1})^p$$ the reason being that the coefficient at $n^{p^2-1}$ is not divisible by $p^2$.
