[Edited to give direct connection with Caporaso-Harris-Mazur via Kevin Buzzard's idea]

Such results are probably true but out of reach of present-day techniques.  For each $p$ or $k$, and every sufficiently large $n$ (say $n>k$), the $n$-term arithmetic progressions of the desired type are parametrized by nontrivial points on some algebraic variety, call it $V_n$, of fixed dimension: dimension $2$ if $p$ is fixed (assuming it's not of the form $a(x-x_0)^k+b$ in which case we're back to Darmon-Merel), and degree about $k$ if $p$ is allowed to vary over all polynomials of degree $k$.  In each case we have for each $n$ two maps $V_n \rightarrow V_{n-1}$ of degree $k$ that forget the first or last term of the progression; and $V_n$ should be of general type for $n$ large enough.  We're now in a setting similar to that of <a href="http://mathoverflow.net/questions/73346">this recent Mathoverflow question</a> (#73346), and I give much the same answer as <a href="http://mathoverflow.net/questions/73346/#73377">I did for that question</a>: the claim should follow from the Bombieri-Lang conjectures plus some possibly nontrivial extra work, as in

> L.Caporaso, J.Harris, and B.Mazur: Uniformity of rational points, *J. Amer. Math. Soc.* **10** #1 (1997), 1-45

but (excluding some very special cases that don't seem relevant here) we have no techniques for proving such results unconditionally on varieties of dimension greater than 1.

**EDIT** Indeed this is a special case of Caporaso-Harris-Mazur, by adapting Kevin Buzzard's observation in his comment on the original question: write the equations as $f(x_m)=m$ $(m=1,2,\ldots,n)$ for some degree-$k$ polynomial $f$ (obtained from $p$ by suitable translation and scaling), and consider just those $m$ in that range which are of the form (say) $y^5$ or $y^5+1$.  By Mason's theorem (polynomial ABC) either $f$ or $f-1$ has at least two zeros whose order is not a multiple of $5$, so either $f(x) = y^5$ or $f(x)=y^5+1$ defines a curve of genus at least $2$.  But the genus is clearly $O(k)$ for any polynomial $f$ of degree $k$.  So, if the number of rational points on such a curve has a uniform bound, then so does the length of an arithmetic progression of values of a polynomial of bounded degree.

Come to think of it, the reduction to C-H-M could also be obtained more directly from the curve $p(x')-p(x)=d$ (for $k>3$), or $p(x''')-p(x'')=p(x'')-p(x')=p(x')-p(x)=d$ (to cover $k=2$ and $k=3$ as well), where $d$ is some multiple of the common difference of the arithmetic progression.