Whereas it is clear that in $L^2[-1,1]$ (as a Hilbert space on $\mathbb{C}$) the span of all monomials $1,x,x^2,x^3,\dots$ is dense (Stone-Weierstrass), and hence its orthogonal complement is $\{0\}$, it is not clear to me how the conclusion changes if one only considers the monomials $x^k,x^{k+1},x^{k+2},\dots$, i.e., starting from some non-zero order $k$.
On the one hand, again by Stone-Weierstrass, it seems correct to me to claim that the subspaces $$ W_k:=\mathrm{span}\{1,x,\dots,x^{k-1}\}\qquad \textrm{and}\qquad V_k:=\mathrm{span}\{x^k,x^{k+1},x^{k+2},\dots\} $$ are linearly independent and that the direct sum $W_k\dotplus V_k$ (namely the polynomials) is dense in $L^2[-1,1]$. I'd be then led to deduce that $$\dim V_k^\perp=\dim W_k=k.$$
On the other hand, it seems also correct to me to say that $$ V_k=\{x^k p\,|\,p\,\textrm{is a polynomial in $x$}\}\,, $$ and therefore, if $u$ is a generic function in $V_k^\perp$, then $$ 0=\int_{-1}^1\overline{u}\,x^k p\,dx\qquad\forall\,\textrm{polynomial } p\,. $$ But then the conclusion seems to be that $x^k u=0$, whence $u=0$ in $L^2[-1,1]$.
Where am I wrong? What is the space $V_k^\perp$ for generic positive integer $k$?
It is the latter conclusion that is true. That is, the dimension of the perpendicular $V_k^\perp$ is $0$, not $k$. Recalling the definition,
$$ V_k^\perp = \{ q \in L^2 : \langle q,p \rangle = 0\ \forall p \in V_k\}$$ Then $1\notin V_k^\perp $ since $V_k$ contains $x^{2N}$ for some $N$, so $$ \langle 1, x^{2N} \rangle = \|x^{2N}\|_{L^1} > 0$$
(this is nothing but a special case of your latter argument)
This makes some sense to me; suppose we wanted to approximate some function $f$ in $L^2$ using only polynomials in $V_k$. Without loss, $f$ is continuous, but we can also further change $f$ into a function $\tilde f$ that is $0$ on a small neighbourhood of $0$ by incurring some small cost $\|f-\tilde f\|_2 < \epsilon$. After doing that, we can approximate $\tilde f/x^k\in C^0$ uniformly with polynomials, so that $$ \|f -px^k\|_2 \le \|f-\tilde f\|_2 + \|\tilde f/x^k -p\|_\infty\|x^k\|_2 \le \epsilon + \|\tilde f/x^k -p\|_\infty\|x^k\|_2 $$ improving the choice of $p$ at this point makes this arbitrarily small, hence the result.