Congruence equation and quadratic residue
An element $x$ of $\bar{\mathbb{F}_p}$ satisfies $$\sum_{k=0}^{M}{M \choose k}^2x^k=0$$ iff the elliptic curve given by the equation $Y^2 = X(X-1)(X-x)$ is supersingular : see the paragraph on the Legendre form of a supersingular elliptic curve on the corresponding wiki page.
These supersingular elliptic curves are all defined over $\mathbb{F}_{p^2}$, but not necessarily over $\mathbb{F}_p$.
The number of such elliptic curves defined over $\mathbb{F}_p$ is equal to (or equal to the half, or equal to twice) the class number of $\mathbb{Q}(\sqrt{-p})$ : see this paper for a precise statement and a modern proof of it.
Now, for $p \equiv 3 \mod 4$, $p \neq 3$, this class number is related to your OEIS sequence by Dirichlet's class number formula.
However, I'm not sure about what happens when $p \equiv 1 \mod 4$.
When $p \equiv 1 \bmod 4$, both expressions are $0$ and I understand why. For $p \equiv 1 \bmod 4$, the number $k$ is a QR iff $p-k$ is. Pairing off $k$ and $p-k$, the OEIS expression is $$\frac{1}{p} \left( \frac{p\cdot \# \mbox{QRs}}{2} - \frac{p \cdot \# \mbox{non-QRs}}{2} \right) = 0.$$
Meanwhile, values of $x$ in $\mathbb{F}_p$ are in bijection with elliptic curves $E$ over $\mathbb{F}_p$ and a chosen bijection between the $\mathbb{F}_p$-points of the $2$-torsion $E[2]$ and $(\mathbb{Z}/2)^2$. As js21 explains, we have $\sum \binom{(p-1)/2}{k}^2 x^k = 0$ if and only if $E$ is supersingular. So we need to show that (when $p \equiv 1 \bmod 4$) there are no supersingular elliptic curves $E$ whose $2$-torsion is entirely defined over $\mathbb{F}_p$.
An supersingular elliptic curve always has $p+1$ points over $\mathbb{F}_p$, so if $p \equiv 1 \bmod 4$ then $\#E(\mathbb{F}_p) \equiv 2 \bmod 4$ and cannot have $(\mathbb{Z}/2 \mathbb{Z})^2$ as a subgroup.
I found the key fact for treating $p \equiv 3 \bmod 4$ in Theorem 2.7 of a paper by Delfs and Galbraith. (See also Galbraith's slides.) If $E$ is a supersingular curve defined over $\mathbb{F}_p$, then Frobenius obeys $\mathrm{Frob}^2 = -p$ and $\mathrm{End}(E) \cap \mathbb{Q}[\mathrm{Frob}]$ is either $\mathbb{Q}\left( \tfrac{1-\sqrt{-p}}{2} \right)$ or $\mathbb{Q}(\sqrt{-p})$. In the former case, Delfs and Galbraith say that the curve is "on the surface", otherwise it is "on the floor". (The metaphor is subterranean, so the floor is below the surface.)
As Theorem 2.7 says, curves on the surface always have three $2$-isogenies from them which are defined over $\mathbb{F}_p$, so their $2$-torsion is entirely defined over $\mathbb{F}_p$, while curves on the floor always have one $2$-isogeny, so their $2$-torsion is not entirely defined over $\mathbb{F}_p$. One can see this directly: $\mathrm{End}(E) \cap \mathbb{Q}[\mathrm{Frob}]$ is $\mathbb{Q}\left( \tfrac{1-\sqrt{-p}}{2} \right)$ iff $[2]$ divides $1-\mathrm{Frob}$, if and only if the kernel of $[2]$ (namely $E(2)$) is contained in the kernel of $1-\mathrm{Frob}$ (namely $E(\mathbb{F}_p)$).
So roots of your polynomial come from curves on the surface -- generally, $6$ roots per curve, but fewer for $j=0$ or $1728$. By a theorem of Deuring, the number of curves on the surface is the same as the number of ideal classes in $\mathbb{Q}\left( \tfrac{1-\sqrt{-p}}{2} \right)$, namely, $h(-p)$.
Combine all of this with Dirichlet's class number formula, and get all the details right, and you should have a proof.
Examples: $p=83$. The class number is $3$ (see here) as is the OEIS sequence. Since $p \equiv 3 \bmod 8$, there are $2 \cdot 3 = 6$ $j$-invariants of supersingular curves defined over $\mathbb{F}_{83}$: $0$, $17$, $28$, $50$, $67$, $68\! \equiv\! 1728$. Each of them has two non-isomorphic twists over $\mathbb{F}_{83}$, so $12$ curves over $\mathbb{F}_{83}$ in all. The $2$-isogenies between them are shown on Galbraith's slide 27. Both of the twists of $j=50$, and one of the twists of $j=1728$, have three $2$-isogenies from them, so $E[2]$ defined over $\mathbb{F}_{83}$.
The roots of your equation over $\mathbb{F}_{83}$ are $2$, $18$, $24$, $39$, $42$, $45$, $60$, $66$, $82$. Of these roots, $2$, $42$ and $82$ correspond to $j=1728$. The other six correspond to one of the two twists with $j=50$; the other twist is $-y^2 = X(X-1)(X-x)$ where $x$ takes one of these six values.
$p=103$: This time, the class number is $5$ and $p \equiv 7 \bmod 8$ so there are $5$ supersingular $j$-invariants in $\mathbb{F}_{103}$: $23$, $24$, $34$, $69$ and $80 \! \equiv \! 1728$. Each of them has two twists. You can see the $2$-isogenies on Slide 33. In particular, the full $2$-torsion is defined over $\mathbb{F}_{103}$ for both twists of $j=23$ and $j=69$, and for one of the twists of $j=1728$.
The roots of your polynomial are $2$, $12$, $25$, $28$, $30$, $33$, $43$, $52$, $61$, $71$, $74$, $76$, $79$, $92$, $102$. As $x$ ranges over these values, $y^2 = X(X-1)(X-x)$ covers $j=1728$ and one of each of the twists of $j=23$ and $j=69$, and $-y^2 = X(X-1)(X-x)$ covers the other twist of the latter cases.