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
Maxwellian electrodynamics fails when quantum mechanical phenomena are involved, in the same way that Newtonian mechanics needs to be replaced in that regime by quantum mechanics. Maxwell's equations don't really "fail", as there is still an equivalent version in QM, it's just the mechanics itself that changes.
Let me elaborate on that one for a bit. In Newtonian mechanics, you had a time-dependent position and momentum, $x(t)$ and $p(t)$ for your particle. In quantum mechanics, the dynamical state is transferred to the quantum state $\psi$, whose closest classical analogue is a probability density in phase space in Liouvillian mechanics. There are two different "pictures" in quantum mechanics, which are exactly equivalent.
In the Schrödinger picture, the dynamical evolution is encoded in the quantum state $\psi$, which evolves in time according to the Schrödinger equation. The position and momentum are replaced by static operators $\hat x$ and $\hat p$ which act on $\psi$; this action can be used to find the expected value, and other statistics, of any measurement of position or momentum.
In the Heisenberg picture, the quantum state is fixed, and it is the operators of all the dynamical variables, including position and momentum, that evolve in time, via the Heisenberg equation.
In the simplest version of quantum electrodynamics, and in particular when no relativistic phenomena are involved, Maxwell's equations continue to hold: they are exactly the Heisenberg equations on the electric and magnetic fields, which are now operators on the system's state $\psi$. Thus, you're formally still "using" the Maxwell equations, but this is rather misleading as the mechanics around it is completely different. (Also, you tend to work on the Schrödinger picture, but that's beside the point.)
This regime is used to describe experiments that require the field itself to be quantized, such as Hong-Ou-Mandel interferometry or experiments where the field is measurably entangled with matter. There is also a large gray area of experiments which are usefully described with this formalism but do not actually require a quantized EM field, such as the examples mentioned by Anna. (Thus, for example, black-body radiation can be explained equally well with discrete energy levels on the emitters rather than the radiation.)
This regime was, until recently, pretty much confined to optical physics, so it wasn't really something an electrical engineer would need to worry about. That has begun to change with the introduction of circuit QED, which is the study of superconducting circuits which exhibit quantum behaviour. This is an exciting new research field and it's one of our best bets for building a quantum computer (or, depending on who you ask, the model used by the one quantum computer that's already built. ish.), so it's something to look at if you're looking at career options ;).
The really crazy stuff comes in when you push electrodynamics into regimes which are both quantum and relativistic (where "relativistic" means that the frequency $\nu$ of the EM radiation is bigger than $c^2/h$ times the mass of all relevant material particles). Here quantum mechanics also changes, and becomes what's known as quantum field theory, and this introduces a number of different phenomena. In particular, the number of particles may change over time, so you can put a photon in a box and come back to find an electron and a positron (which wouldn't happen in classical EM).
Again, here the problem is not EM itself, but rather the mechanics around it. QFT is built around a concept called the action, which completely determines the dynamics. You can also build classical mechanics around the action, and the action for quantum electrodynamics is formally identical to that of classical electrodynamics.
This regime includes pair creation and annihilation phenomena, and also things like photon-photon scattering, which do seem at odds with classical EM. For example, you can produce two gamma-ray beams and make them intersect, and they will scatter off each other slightly. This is inconsistent with the superposition principle of classical EM, as it breaks linearity, so you could say that the Maxwell equations have failed - but, as I pointed out, it's a bit more subtle than that.