Is this an issue with the law of the excluded middle, or an issue with the proof?

Ignore the broader proof - do you agree with the assertion "If $x$ is divisible by $4$, then $x$ is even?" This is all that's going on. We're always allowed to "forget" information in a proof, and this has nothing to do with the excluded middle. When you conclude "$x^2$ is even," this in no way implies that you've concluded "$x^2$ is even and that's the most that can be said."

If you're in Paris, then you're in Europe. Even more particularly, you're in France. However, "if you're not in Europe, then you're not in Paris," is still a valid application of the contrapositive, even though we've "forgotten" the information about being in France.

"You're in Paris." $\longleftrightarrow x$ is even.

"You're in Europe." $\longleftrightarrow x^2$ is even.

"You're in France." $\longleftrightarrow x^2$ is a multiple of $4$.

It is not a law of excluded middle that you need to prove that every integer is either even or odd. Excluded middle applies equally to integers and reals, but not every real is even or odd. To prove this property requires a property of integers, such as the division algorithm (divide by 2, look at remainder).