Let $X_n$, $n\geqslant 1$ be i.i.d. random variables with $\mathbb P(X_1=1)=\frac12=\mathbb P(X_1=-1)$ and define $S_n = \sum_{k=1}^n X_k$. Let $P\in\mathbb R[x,y]$ be a polynomial in two real variables. I have read the claim
$P(S_n,n)$ is a martingale if and only if $$P(s+1,n+1) + P(s-1,n+1) = 2P(s,n).\tag 1$$
Note that $\mathbb E[|P(S_n,n)|]<\infty$ since it is a finite sum of bounded random variables, so we need only consider the martingale criteria $$ \mathbb E[P(S_{n+1},n+1)\mid \mathcal F_n] = P(S_n,n),\tag 2 $$ where $\mathcal F_n = \sigma(X_1,\ldots,X_n)$. Claims $(1)$ and $(2)$ clearly hold for the constant polynomial $1$. If $P(S_n,n)=S_n$ then $$ \mathbb E[S_{n+1}\mid\mathcal F_n] = \mathbb E[S_n + X_{n+1}\mid\mathcal F_n] = \mathbb E[S_n\mid\mathcal F_n] + \mathbb E[X_{n+1}\mid\mathcal F_n] = S_n + 0 = S_n, $$ and also $$ P(S_n+1,n+1) + P(S_n-1,n+1) = (S_n+1)+(S_n-1) = 2S_n = 2P(S_n,n), $$ So $(1)$ and $(2)$ hold for $P(S_n,n)=S_n$. Further, we see that \begin{align}\mathbb E[S_{n+1}^2\mid\mathcal F_n] &= \mathbb E[S_n^2\mid\mathcal F_n] +2\mathbb E[S_nX_{n+1}\mid\mathcal F_n] + \mathbb E[X_{n+1}^2\mid\mathcal F_n]\\ &= S_n^2 + 2\mathbb E[X_{n+1}]S_n + \mathbb E[X_{n+1}^2]\\ &= S_n^2 + 1, \end{align} so setting $P(S_n,n) = S_n^2-n$, we have $$ \mathbb E[P(S_{n+1},n+1)\mid\mathcal F_n] = S_n^2 + 1 -(n+1) = S_n^2-n = P(S_n,n), $$ so that $S_n^2-n$ is a martingale. We verify that \begin{align} P(s+1,n+1)+P(s-1,n+1) &= (s+1)^2 -(n+1) + (s-1)^2 -(n+1)\\ &= 2s^2 -2(n+1) + 2\\ &= 2(s^2-n)\\ &= 2P(s,n). \end{align}
We may continue this process by the polynomials $S_n^3-3nS_n, S_n^4-6nS_n^2+2n+3n^2$, and so on. But how do we see that $(1)$ and $(2)$ are equivalent?
Note that condition (1) is equivalent to $$P(s,n) = \frac{P(s+1,n+1)+P(s-1,n+1)}{2}.$$ Now, \begin{align*} \mathbb{E}[P(S_{n+1},n+1)\mid \mathcal{F}_n] &= \sum_{s \in \mathbb{Z}}\mathbb{E}[P(S_{n+1},n+1)1\{S_{n}=s\}\mid \mathcal{F}_n]\\ &= \sum_{s \in \mathbb{Z}}1\{S_{n}=s\}\mathbb{E}[P(s+X_{n+1},n+1)]\\ &=\sum_{s \in \mathbb{Z}} 1\{S_n=s\} \frac{P(s+1,n+1)+P(s-1,n+1)}{2}\\ &=\sum_{s \in \mathbb{Z}} 1\{S_n=s\}P(s,n)\\ &=P(S_n,n). \end{align*}
So condition (1) implies condition (2).
For the reverse, we assume $P(S_n,n)$ is a martingale. That is, $\mathbb{E}[P(S_{n+1},n+1)\mid \mathcal{F}_n]=P(S_n,n)$. Note that for any $s \in \mathbb{Z}$ we can multiply this equation by $1\{S_n=s\}$ to get: \begin{align*} 1\{S_n=s\}\mathbb{E}[P(S_{n+1},n+1)\mid \mathcal{F}_n] &=1\{S_n=s\}P(S_n,n)\\ 1\{S_n=s\}\mathbb{E}[P(s+X_{n+1},n+1)\mid \mathcal{F}_n]&=1\{S_n=s\}P(s,n)\\ 1\{S_n=s\} \frac{P(s+1,n+1)+P(s-1,n+1)}{2}&=1\{S_n=s\}P(s,n). \end{align*} Therefore, if $S_n=s$ occurs with positive probability, we have $\frac{P(s+1,n+1)+P(s-1,n+1)}{2}=P(s,n)$. This assumption is actually necessary. For instance, I could change the values of $P(99,1)$, $P(100,1)$, and $P(101,1)$ such that $P(99,1)+P(101,1) \neq 2 P(100,1)$ and $P(S_n,n)$ would still be a martingale since $S_1$ is far away from $100$.