If it satisfies a linear difference equation with characteristic polynomial $(1-t)^m $ for some m, the sequence is a polynomial.

If it satisfies a linear difference equation with characteristic polynomial $(t-1)^m $ for some $m$, the sequence is a polynomial.

This is essentially equivalent to the statement by Gerald Edgar in a comment, that taking iterated differences, we eventually reach a constant sequence.

So, more formally, $\{s_n\}$ is a sequence that is given by a polynomial iff there is an $m$ such that $$ \sum_{j=0}^m s_{i+j} (-1)^j\binom{m}{j} = 0$$ for all $i$. Note that $\sum_{j=0}^m t^j (-1)^j\binom{m}{j} =(t-1)^m$, which explains the connection.

For example, my favourite proof that the number of skew semi-standard Young tableaux of shape $n\lambda$, is a polynomial in $n$, uses this observation. I recently put a paper on arxiv that basically uses this idea.

A third way to reformulate this, is that the generating function can be expressed as $$\sum_{j=0}^\infty s_i t^i = \frac{c_0 + c_1t \cdots + c_{m-1}t^{m-1}}{(1-t)^m}$$ for some $c_i$.