To begin with, Maxwell's equations are vector partial differential equations, which makes their solution intrinsically more difficult than that of scalar partial differential equations.
To help obviate this difficulty, an ansatz was long ago made (by Hertz himself, perhaps?) who proposed two useful categories of wave solution: transverse electric (TE), and transverse magnetic (TM). The term 'Transverse' here means 'transverse to the waveguide axis', which is conventionally the 'z' direction, and the presumed direction of propagation.
These categories are somewhat self-explanatory. TM waves have no z directed magnetic field component, and TE waves have no z directed electric field component. Each of these is derivable as the curl of an appropriate vector potential, magnetic or electric. If the idea of an electric vector potential is troublesome to you, try the book by Harrington 'Time Harmonic Electromagnetic Fields.' (With no denigration of Griffiths, I advise that you widen the scope of your reading.) In either case the vector potential is assumed to have a single, z-directed, component, comprising a scalar function of the form f(x,y)exp(ikz). This entire scalar function is presumed to satisfy the scalar Helmholtz equation (with propagation constant k), which insures that taking its curl (and the curl of the resultant) will lead to Maxwell's equations.
In essence, TE and TM waves are assumed; these ideas came out of someone's brain. Their justification is that they lead us (as noted) to Maxwell's equations, and from there to innumerable useful solutions and applications. Inasmuch as a waveguide is designed to propagate a monochromatic wave of some chosen frequency, the simplest form of traveling wave solution is exp(ikz), as noted. As far as why one wants a monochromatic wave, one answer would be that (at a guess) >90 % of communication electronics involves the modulation of a carrier wave, with the frequency bandwidth of modulation typically small in comparison to the carrier frequency.
Sorry to go on at such length. I hope this helps.
The most important statement in this answer to your question is: Yes, you can superimpose a constant magnetic field. The combined field remains a solution of Maxwell's equations. $\def\vB{{\vec{B}}}$
$\def\vBp{{\vec{B}}_{\rm p}}$
$\def\vBq{{\vec{B}}_{\rm h}}$
$\def\vE{{\vec{E}}}$
$\def\vr{{\vec{r}}}$
$\def\vk{{\vec{k}}}$
$\def\om{\omega}$
$\def\rot{\operatorname{rot}}$
$\def\grad{\operatorname{grad}}$
$\def\div{\operatorname{div}}$
$\def\l{\left}\def\r{\right}$
$\def\pd{\partial}$
$\def\eps{\varepsilon}$
$\def\ph{\varphi}$
Since you are using plane waves you even cannot enforce the fields to decay sufficiently fast with growing distance to the origin. That would make the solution of Maxwell's equations unique for given space properties (like $\mu,\varepsilon,\kappa$, and maybe space charge $\rho$ and an imprinted current density $\vec{J}$). But, in your case you would not have a generator for the field. Your setup is just the empty space. If you enforce the field to decay sufficiently fast with growing distance you just get zero amplitudes $\vec{E}_0=\vec{0}$, $\vec{B}_0=\vec{0}$ for your waves. Which is certainly a solution of Maxwell's equations but also certainly not what you want to have.
For my point of view you are a bit too fast with the integration constants. You loose some generality by neglecting that these constants can really depend on the space coordinates.
Let us look what really can be deduced for $\vB(\vr,t)$ from Maxwell's equations for a given
$\vE(\vr,t)=\vE_0 \cos(\vk\vr-\om t)$ in free space.
At first some recapitulation:
We calculate a particular B-field $\vBp$ that satisfies Maxwell's equations:
$$
\begin{array}{rl}
\nabla\times\l(\vE_0\cos(\vk\vr-\om t)\r)&=-\pd_t \vBp(\vr,t)\\
\l(\nabla\cos(\vk\vr-\om t)\r)\times\vE_0&=-\pd_t\vBp(\vr,t)\\
-\vk\times\vE_0\sin(\vk\vr-\om t) = -\pd_t \vBp(\vr,t)
\end{array}
$$
This leads us with $\pd_t \cos(\vk\vr-\om t) = \om \sin(\vk\vr-\om t)$ to the ansatz
$$
\vBp(\vr,t) = -\vk\times\vE_0 \cos(\vk\vr-\om t)/\om.
$$
The divergence equation $\div\vBp(\vr,t)=-\vk\cdot(\vk\times\vE_0)\cos(\vk\vr-\om t)/\om=0$ is satisfied and the space-charge freeness
$0=\div\vE(\vr,t) = \vk\cdot\vE_0\sin(\vk\vr-\om t)$ delivers that $\vk$ and $\vE_0$ are orthogonal. The last thing to check is Ampere's law
$$
\begin{array}{rl}
\rot\vBp&=\mu_0 \eps_0 \pd_t\vE\\
\vk\times(\vk\times\vE_0)\sin(\vk\vr-\om t)/\om &= -\mu_0\eps_0 \vE_0 \sin(\vk\vr-\om t) \om\\
\biggl(\vk \underbrace{(\vk\cdot\vE_0)}_0-\vE_0\vk^2\biggr)\sin(\vk\vr-\om t)/\om&= -\mu_0\eps_0 \vE_0 \sin(\vk\vr-\om t) \om
\end{array}
$$
which is satisfied for $\frac{\omega}{|\vk|} = \frac1{\sqrt{\mu_0\eps_0}}=c_0$ (the speed of light).
Now, we look which modifications $\vB(\vr,t)=\vBp(\vr,t)+\vBq(\vr,t)$ satisfy Maxwell's laws.
$$
\begin{array}{rl}
\nabla\times\vE(\vr,t) &= -\pd_t\l(\vBp(\vr,t)+\vBq(\vr,t)\r)\\
\nabla\times\vE(\vr,t) &= -\pd_t\vBp(\vr,t)-\pd_t\vBq(\vr,t)\\
0 &= -\pd_t\vBq(\vr,t)
\end{array}
$$
That means, the modification $\vBq$ is independent of time. We just write $\vBq(\vr)$ instead of $\vBq(\vr,t)$.
The divergence equation for the modified B-field is $0=\div\l(\vBp(\vr,t)+\vBq(\vr)\r)=\underbrace{\div\l(\vBp(\vr,t)\r)}_{=0} + \div\l(\vBq(\vr)\r)$ telling us that the modification $\vBq(\vr)$ must also be source free:
$$
\div\vBq(\vr) = 0
$$
Ampere's law is
$$
\begin{array}{rl}
\nabla\times(\vBp(\vr,t)+\vBq(\vr)) &= \mu_0\eps_0\pd_t \vE,\\
\rot(\vBq(\vr))&=0.
\end{array}
$$
Free space is simply path connected. Thus, $\rot(\vBq(\vr))=0$ implies that every admissible $\vBq$ can be represented as gradient of a scalar potential $\vBq(\vr)=-\grad\ph(\vr)$.
From $\div\vBq(\vr) = 0$ there follows that this potential must satisfy Laplace's equation
$$
0=-\div(\vBq(\vr)) = \div\grad\ph = \Delta\ph
$$
That is all what Maxwell's equations for the free space tell us with a predefined E-field and without boundary conditions:
The B-field can be modified through the gradient of any harmonic potential.
The thing is that with problems in infinite space one is often approximating some configuration with finite extent which is sufficiently far away from stuff that could influence the measurement significantly.
How are plane electromagnetic waves produced?
One relatively simple generator for electromagnetic waves is a dipole antenna. These do not generate plane waves but spherical curved waves as shown in the following nice picture from the Wikipedia page http://en.wikipedia.org/wiki/Antenna_%28radio%29.
Nevertheless, if you are far away from the sender dipol and there are no reflecting surfaces around you then in your close neighborhood the electromagnetic wave will look like a plane wave and you can treat it as such with sufficiently exact results for your practical purpose.
In this important application the plane wave is an approximation where the superposition with some constant electromagnetic field is not really appropriate.
We just keep in mind if in some special application we need to superimpose a constant field we are allowed to do it.
Best Answer
By definition, an electromagnetic wave is a solution to Maxwell's equations in vacuum. The electric field of a EM wave solution is always perpendicular to the direction of propagation. Let me denote this electric field by $\vec{E}_{EM}$. If $\vec{v}$ is the velocity of the wave, then we must have $\vec{E}_{EM} \cdot \vec{v} = 0 $.
However, Maxwell's equations are linear equations and in particular allow for superposition of solutions. By cleverly choosing sources, it seems entirely likely that we can construct an electric field generated by the source $\vec{E}_{source}$ in such a way that the total electric field $\vec{E}_T = \vec{E}_{EM} + \vec{E}_{source}$ is parallel to $\vec{v}$.
Further, due to the superposition princpiple, if $\vec{E}_{EM}$ and $\vec{E}_{source}$ satisfy Maxwell's equations then so does $\vec{E}_T$.