My claim is that the maximal submodules of $\mathbb Z[x]$ have the following form: $$ p\mathbb Zx^n+ \sum_{k\not=n}\mathbb Zx^k $$ for some prime $p$ and nonnegative $k$.
Here's what I have. Let $M$ be a maximal ideal of $\mathbb Z[x]$. For $n\ge 0$ define $M_n$ to be $M\cap\mathbb Z x^n$, i.e., $0$ and monomials of degree $n$ in $M$. Then since $M\not=\mathbb Z[x]$, for some $n$ we have $M_n\not=\mathbb Z x^n$. Now here I would like to say that we have $M_n\not=\mathbb Z x^n$ for at most one $n$ by maximality (this would complete the proof), but I'm not confident. I would appreciate a counterexample, or else help completing this proof.
You are not quite right.
A $\mathbb{Z}$-module is the same as an abelian group. Thus, you're asking for the maximal subgroups of the abelian group $\mathbb{Z}[x]$. As an abelian group, $\mathbb{Z}[x]$ is free of countable rank, with basis $1 = x^0,x^1,x^2,\ldots$. Clearly any subgroup of prime index is maximal, so we want to characterize the subgroups of prime index. Any such subgroup appears as the kernel of some surjective group homomorphisms $\mathbb{Z}[x]\rightarrow\mathbb{Z}/p\mathbb{Z}$ (because quotienting out by any such subgroup gives you such a surjective homomorphism), so we want to understand such surjections. (This also tells you that every maximal subgroup has prime index, since quotienting out by a maximal subgroup will necessarily give us a simple abelian group, which are precisely the cyclic groups of prime order)
Any homomorphism $\mathbb{Z}[x]\rightarrow\mathbb{Z}/p$ is determined by where you send $1 = x^0,x^1,x^2,\ldots$, and since they are a basis for $\mathbb{Z}[x]$, you can send them anywhere. The homomorphism you get is surjective iff they are not all sent to 0.
If you send some $x^j$ to 1 and $x^i$ to 0 for all $i\ne j$, then the kernel is of the form you describe, but of course not all surjections arise in this manner. For example, you could send each $x^i$ to 1, in which case the kernel (ie, maximal subgroup) can be described as the set of all polynomials in $\mathbb{Z}[x]$ whose coefficients sum to a multiple of $p$.
Your mistake is similar to the classic linear algebra mistake of thinking that every vector subspace of say, the plane $\mathbb{R}^2$ is given by one of the axes, or is generated by one of the basis vectors, but you have to remember that the choice of basis was arbitrary - there's nothing special about the basis you chose, and any (nonzero) vector can be included in some basis.