As noted by Douglas Zare, $x^{16} + x^{12} + x^5 + 1 = (x+1)g_{15}(x)$, where $g_{15}(x) := x^{15}+x^{14}+x^{13}+x^{12}+x^4+x^3+x^2+x+1$.
Let $Q:=\mathbb{F}_2[x]/\langle g_{15}(x)\rangle$ be the factor-ring of polynomials over $\mathbb{F}_2$ modulo $g_{15}(x)$. (Since $g_{15}$ is irreducible, $Q$ is isomorphic to $GF(2^{15})$ and thus has $2^{15}$ elements).
For any nonnegative integers $N,k$ and any $q(x)\in Q$, let $h_k(N,q)$ be the number of $k$-nomials $f(x)$ of degree $\leq N$ such that $f(x)\equiv q(x)\pmod{g_{15}(x)}$.
Clearly, $h_0(N,q(x)) = 0$ unless $q(x)= \mathbf{0}$, and $h_0(N,\mathbf{0}) = 1$.
For $k\geq 1$, we have $$h_k(N,q(x)) = \sum_{j=1}^N h_{k-1}(j-1,q(x)-x^j),$$ which allows to recursively compute $h_k(N,q(x))$. The answer to the first question for even $k$ is given by $h_k(N,\mathbf{0})$. Using dynamic programming, this computation will take $O(kn^2)$ arithmetic operations.