Correction to the derivation in the question, as per the comment under it:
Your error is here: "If we approximate the wave as a plane wave, so
that along a given $\hat{x}−\hat{y}$ plane the E field is constant at a fixed
time....", instead at a fixed time in any direction you have still a
sinusoidal spatial distribution of the field components. Only the
amplitude of the sinusoidal distribution is constant
I found a satisfying answer in the Feynman Lecture's on physics (Ch 20)
One part of the derivation I was missing was Ampere's law
$$\nabla \times B = \mu_0 J + \mu_0\epsilon_0\frac{\partial E}{\partial t}.$$
In the source free ($J = 0$) case in free space ($\mu_0 \epsilon_0 = 1/c_0^2$) this reduces to
$$c_0^2 \nabla \times B = \frac{\partial E}{\partial t}.$$
But by the plane wave approximation, the $B$ field doesn't vary on the $\hat{x}-\hat{y}$ plane ($\nabla \times B \cdot \hat{z} = 0$), so $E_z$ is constant with respect to time.
Now, using the explanation in my original question, we have that $E_z = C(x, y)$. This means that our model may be applied in the case of a DC electric field $C = C(x, y)$ projected onto the $\hat{x}-\hat{y}$ plane (e.g. due to a capacitor-type plate).
Now our knowledge of the physical nature of electromagnetic waves, rather than mathematics comes into play. If our wave has a $\hat{z}$ component, it must be constant with respect to time. But this does not describe an electromagnetic wave, hence we set $C = 0.$
To elaborate, in the freespace sourceless case, the Maxwell's equations that are relevant to wave propagation are Faraday's law and Ampere's law:
$$ \nabla \times E = \frac{-\partial B}{\partial t}, \qquad
c_0^2 \nabla \times B = \frac{\partial E}{\partial t}.
$$
Hence, if either of the time derivatives are zero, then we're doing electrostatics or magnetostatics, which we're not interested in. In cases where constant fields are present, these can be considered individually and then combined using the principle of superposition.
Let us now repeat the argument we used for electric fields and apply it to magnetic fields. From Maxwell's equations
$$
0 = \nabla \cdot B =
\frac{\partial B_x}{\partial x} +
\frac{\partial B_y}{\partial y} +
\frac{\partial B_z}{\partial z}
=
\frac{\partial B_z}{\partial z}
$$
since the magnetic field is constant on the $\hat{x}-\hat{y}$ plane by the plane-wave assumption. Further, by this assumption
$$ 0 = \nabla \times E \cdot \hat{z} \qquad \text{so} \qquad 0 = \frac{-\partial B_z}{\partial t}
$$
Hence $B_z = D(x,y)$ for some non-time varying $D$. Hence $B_z = 0$ by the same reasoning used for electric fields.
Why $E$ and $B$ are orthogonal, and orthogonal to the direction of propagation, for plane waves, as described by the diagram above.
Hence Faraday's law and Ampere's law give us that the dynamically varying components of $E$ and $B$ are mutually orthogonal, so in the absence of a magnetic field $E$ and $B$ are orthogonal in fact. However, a static electric or magnetic charge does not effect $\nabla \times E$, $\nabla \times B$, or the time derivatives of $E$ or $B$ - that is, the DC component of each side of the Ampere's law and Faraday's law equations vanish while taking derivatives. Now since wave propagation is determined solely by the dynamically varying component of $E$ and $B$, the Poynting vector $E \times B$ isn't necessarily in the direction of propagation, which is instead in the direction of $E_{\text{dynamically varying}} \times B_{\text{dynamically varying}}$.
Answer for sinosoidal plane waves:
Let $k$ be the direction of propagation. Also
let $E = E_0 e^{\pm jk \cdot r}$, as in Nephente's answer, except in phasor (time-harmonic) form we ignore the time dependent term. Note that the time domain expression for the electrical field is given by $\Re\{E_0 e^{j\omega t\pm jk \cdot r}\}.$
Let $E_0 = (A_x, A_y, A_z)$ so $E_x = A_x e^{\pm jk \cdot r}$ and
$$
\frac{\partial E_x}{\partial x}
= A_x e^{\pm jk \cdot r} \frac{\partial}{\partial x} (\pm jk \cdot r)
= A_x e^{\pm jk \cdot r} (\pm j) \frac{\partial}{\partial x} (x k_x + y k_y + z k_z)
= A_x (\pm j) k_x.
$$
Hence
$$
\nabla \cdot E
= (\pm j)(A_x k_x + A_y k_y + A_z k_z)
= (\pm j)(E_0 \cdot k)
$$
so in the sourceless case ($\nabla \cdot E = 0$), $0 = k \cdot E.$
Hence the electric field in the direction of $k$ is zero, or in other words, the electric field is orthogonal to the direction of propagation.
The reason we're able to derive this result without assumptions about static electric fields is that our phasor model is essentially a sinosoidal ansatz.
