If this were known for $k=2$, it would mean that for sufficiently large $n$ and some $A$, there is always a prime between $n^2$ and $(n+A)^2$. I believe that this is still open; see Legendre's conjecture. For comparison, the Riemann Hypothesis would imply there is a prime between $n^2$ and $(n+A \log n)^2$.
It is known that for large enough $n,$ there are primes between $n^3$ and $(n+1)^3$ (and you can lower that exponent from $3$). Perhaps you can use this to construct sequences with some differences bounded, although this is not immediate to me.
