De Bruijn's sequence is odd iff $n=2^m-1$: Part I

That's true. This follows easily from the formula $$ \hat{S}(4,n)=\frac1{n+1}\binom{2n}n\sum_{k=0}^n (-1)^k\binom{2n+k}k^2\binom{2n}{n+k}.\quad\quad\quad\quad\quad(*) $$

First of all, I prove your parity claim using $(*)$, and next prove $(*)$. If $n+1$ is not a power of 2, then $C_n=\frac1{n+1}\binom{2n}n$ is even and so is RHS of $(*)$. If $n=2^m-1$, then $C_n$ is odd, the summand with $k=1$ in RHS of $(*)$ is odd and other summands are even: $\binom{2n+k}k=\frac{(2n+1)(2n+2)}{k(k-1)}\binom{2n+k}{k-2}$ is even for $k=2,3,\ldots,n$ since $k(k-1)$ is not divisible by $2^{m+1}=2n+2$.

Now the proof of $(*)$. For $C:=(-1)^n (n+1)\hat{S}(4,n)$ we have $$C=[x^{2n}y^{2n}z^{2n}t^{2n}](x-y)^{2n}(y-z)^{2n}(z-t)^{2n}(x+t)^{2n}=[x^{2n}y^{2n}z^{2n}t^{2n}]F,$$ where $$F=\prod_{j=-(n-1)}^{n}(x-y-j)(z-y-j)(z-t-j)(x+t-2n-j).$$ Denote $A=\{0,1,\ldots,2n\}$ and express the coefficient $[x^{2n}y^{2n}z^{2n}t^{2n}]F$ via the values of $F$ on $A^4$ using this formula.

Look how $F(x,y,z,t)\ne 0$ may be possible when $x,y,z,t\in A$. We must have $|x-y|\geqslant n, |y-z|\geqslant n, |z-t|\geqslant n$ and $x-y\ne n$, $z-y\ne n$, $z-t\ne n$. If $y$ lies between $x$ and $z$, the conditions $|x-y|\geqslant n, |z-y|\geqslant n$ yield $y=n$, $\{x,z\}=\{0,n\}$, but then either $x-y$ or $z-y$ equals $n$; a contradiction. Analogously if $z$ lies between $y$ and $t$. Thus $x-y,z-y,z-t$ have equal sign. If they are positive, we get $2n\geqslant x\geqslant y+n+1\geqslant n+1$ and $n-1\geqslant z-n-1\geqslant t\geqslant 0$, thus $x+t\in [n+1,3n-1]$ and therefore $F(x,y,z,t)=0$; a contradiction. So we must have $n\geqslant y-n\geqslant x\geqslant 0$, $2n\geqslant t\geqslant z+n\geqslant n$ and $x+t\in [n,3n]$. Since $F(x,y,z,t)\ne 0$, we conclude that $x+t=n$, $x=0$, $t=n$, thus $z=0$ and $y\in [n,2n]$. Then the cited formula allows to rewrite $C$ as a sum over $y$ which simplifies as $(*)$.

I just wished to suggest an alternative (mechanical) proof whose details can be provided (using the WZ-method) for the identity $$\sum_{k=0}^{2n}(-1)^{n+k}\binom{2n}k^4=\binom{2n}n\sum_{k=0}^n(-1)^k\binom{2n+k}k^2\binom{2n}{n+k}.\qquad \qquad (*)$$ The idea is: verify that both sides of $(*)$ satisfy the 2nd-order recurrence \begin{align*} A(n)a(n+2)- B(b)a(n+1) +C(n)a(n)=0 \end{align*} with initial conditions $a(0)=1$ and $a(1)=14$; where \begin{align*} A(n)&=(2n + 3)(48n^2 + 66n + 23)(n + 2)^3 \\ B(n)&=13056n^6+ 96288n^5+ 289600n^4+ 453428n^3 + 388698n^2 + 172598n+31030 \\ C(n)&=4(n + 1)(48n^2 + 162n + 137)(2n + 1)^3. \end{align*}