$\prod_k(x\pm k)$ in binomial basis?

It is sufficient to prove that the two sides agree when $x = n + \ell$ for $\ell \in \mathbb{N}$. As $k$ varies, the first term in $\prod_{k=1}^n (k-n-\ell)(k+n+\ell)$ contributes

$$-\ell(-\ell-1) \ldots (-\ell-n+1) = (-1)^n (\ell+n-1)\ldots (\ell+1)\ell$$

and the second term contributes $(n+\ell+1)\ldots (2n+\ell)$. Taking into account the factor $x$ before the product, the left-hand side is therefore

$$(-1)^n \frac{(2n+\ell)!}{(\ell-1)!}.$$

The right-hand side can be rewritten as follows:

$$\begin{align*} \frac{1}{4^n}{}&{} \sum_{m=0}^n \binom{-\ell}{m}\binom{2n+\ell}{n-m}(2m+\ell)^{2n+1} \\ &= \frac{1}{4^n} \sum_{m=0}^n (-1)^m \binom{m+\ell-1}{m}\binom{2n+\ell}{n-m}(2m+\ell)^{2n+1} \\ &= \frac{(-1)^n}{4^n} \sum_{m=0}^n (-1)^m \binom{n-m+\ell-1}{\ell-1} \binom{2n+\ell}{m} (2n-2m+\ell)^{2n+1} \\ &= \frac{(-1)^n}{2.4^n} \sum_{m=0}^{2n+\ell}(-1)^m \binom{2n+\ell}{m} \binom{n-m+\ell-1}{\ell-1} (2n-2m+\ell)^{2n+1} \end{align*}$$

where the sum may be extended to get the final line using $\binom{n-m+\ell-1}{\ell-1} = \binom{\ell-\beta-1}{\ell-1} = 0$ if $m = n + \beta$ with $\beta \in \{1,\ldots, \ell-1\}$ and the equality of the summands for $m=n+\ell+\alpha$ and $m = n-\alpha$ for $\alpha \in \{0,1,\ldots,n\}$; this follows from $\binom{-1-\alpha}{\ell-1} = \binom{\ell+\alpha-1}{\ell-1}(-1)^{\ell-1}$ and $\binom{2n+\ell}{n+\ell+\alpha} = \binom{2n+\ell}{n-\alpha}$.

Therefore, up to the multiple $(-1)^n/2^{2n+1}$, the right-hand side is the $(2n+\ell)$th (backwards) iterated difference of the polynomial $y \mapsto \binom{y+\ell-1}{\ell-1}(2y+\ell)^{2n+1}$ of degree $2n+\ell$, evaluated at $y=n$. In fact the evaluation point makes no difference: we always get $(2n+\ell)!$ times its leading coefficient, namely $2^{2n+1}/(\ell-1)!$. Hence the right-hand side is

$$(-1)^n \frac{(2n+\ell)!}{(\ell-1)!},$$

as required.

Here is an argument for the leading coefficient (and more).

We use (formal) generating functions. Let $f_{n,x}(t):= \sum_{m=0}^n {n-x \choose m } {n+x \choose n-m} e^{(x+2m-n)t}$, we are interested in the polynomial $q_n(x)=\frac{(2n+1)!}{4^n}\;[t^{2n+1}]\,f_{n,x}(t)$. Clearly \begin{align*} f_{n,x}(t)&=[z^n] e^{tx}\,\left(1+ze^t\right)^{n-x}\left(1+ze^{-t}\right)^{n+x}\\ &=[z^n]\left(\frac{e^{t}\,(1+ze^{-t})}{1+ze^t}\right)^x \left(1+ 2z\cosh(t) +z^2\right)^{n}\\ &=[z^n] (g_{t}(z))^x\,\left(1+ 2z\cosh(t) +z^2\right)^{n} \end{align*} where $g_{t}(z):=\frac{e^{t}\,(1+ze^{-t})}{1+ze^t}$. Thus (by the Lagrange-Bürmann theorem)
$$G_x(u):=\sum_{n=0}^\infty f_{n,x} u^n = \frac {(g_t(w))^x}{1-u(2\cosh(t)+2w)}$$ where $w=w(u)$ solves $w=u\left(1+w\cosh(t)+w^2\right)$ with $w(0)=0$.

In the sequel let $c:=\cosh(t), s:=\sinh(t)$. We find \begin{align*} w(u)&=\frac{1}{2u}-c - \sqrt{(c-\frac{1}{2u})^2-1)}\\[0.1cm] 1-2u(c+w)&=\sqrt{(1-2cu)^2 -4u^2}\\[0.1cm] %=\sqrt{1-4cu +4s^2 u^2}\\ g_t(w)&=c-2s^2u +s \sqrt{1-4cu +4s^2 u^2} \end{align*}

so that
$$G_x(u)=\frac{\left(c-2s^2u +s \sqrt{1-4cu +4s^2 u^2}\right)^x}{\sqrt{1-4cu +4s^2 u^2}}$$

Observe that the numerator of $G_x$ is of the form $(z+\sqrt{1+z^2})^x$ where $z=s \sqrt{1-4cu +4s^2 u^2}$.

Now consider $$f(z)=\left(z+\sqrt{1+z^2}\right)^x=\sum_{n\geq 0}c_nz^n$$ Since $f$ satisfies the linear differential equation $$(1+z^2)f^{\prime\prime}-x^2f=-zf^\prime$$ with $f(0)=1,\,f^\prime(0)=x$, the coefficients satisfy the recursion $c_0=1, c_1=x$ and $$(n+2)(n+1) c_{n+2}=(x^2-n^2) c_n\;.$$ Thus the coefficients $c_n$ are of the form $c_n=\frac {p_n(x)}{n!}$, where each $p_n(x)$ is a monic polynomial of degree $n$ in $x$, and we may write $$G_x(u)=\sum_{k\geq 0}\frac{s^{k}p_k(x)}{k!} \left(\sqrt{1-4cu +4s^2 u^2}\right)^{k-1}\;.$$ Now extract $[u^nt^{2n+1}]G_x(u)=\frac{4^n}{(2n+1)!} q_n(x)$. Since $c$ and $s^2$ are even functions of $t$ only the summands with odd powers of $s$ can have non-vanishing coefficient of $t^{2n+1}$, and since the series of $s$ starts with $t$ only summands with $k\leq 2n+1$ contribute. Thus the highest power of $x$ in $q_n(x)$ is at most $2n+1$ and can only appear in $p_{2n+1}$, and since $p_{2n+1}$ is monic the coefficient of $x^{2n+1}$ is $$\frac{(2n+1)!}{4^n}[t^{2n+1}u^{n}]\frac{s^{2n+1}}{(2n+1)!} \left(1-4cu +4s^2 u^2\right)^{n}=(-1)^n\;,$$ as desired. Now Brendan McKay's argument above shows the desired equality.