The apparent paradox can be analyzed more clearly if we simplify it a bit. Let's assume we have one object with mass $M$ emitting two photons in opposite directions, each of them with momentum $p$.
In the rest frame of the object, choosing the X-axis to align with the emitted photons, we will have the following four-momenta (using units where $c = 1$):
Before
$p_{obj}^{before} = [M,0,0,0]$
After
$p_{obj}^{after} = [M-2p,0,0,0]$
$p_{\gamma_1} = [p,p,0,0]$
$p_{\gamma_2} = [p,-p,0,0]$
Here we clearly have four-momentum conservation:
$p_{obj}^{before} = p_{obj}^{after} + p_{\gamma_1} + p_{\gamma_2}$
As this is a Lorentz-invariant four-vector equation, it will be valid in any reference frame.
To see it more explicitly, let's boost the system by a speed $v$ in the +X direction and see how the equations look then:
Before
$p_{obj}^{before} = \left[M\,(1-v^2)^{-1/2},M\,v\,(1-v^2)^{-1/2},0,0\right]$
After
$p_{obj}^{after} = \left[(M-2p)\,(1-v^2)^{-1/2},(M-2p)\,v\,(1-v^2)^{-1/2},0,0\right]$
$p_{\gamma_1} = \left[p(1-v^2)^{-1/2}+p\,v\,(1-v^2)^{-1/2},p(1-v^2)^{-1/2}+p\,v\,(1-v^2)^{-1/2},0,0\right]$
$p_{\gamma_1} = \left[p(1+v)(1-v^2)^{-1/2},p(1+v)(1-v^2)^{-1/2},0,0\right]$
$p_{\gamma_2} = \left[p(1-v)(1-v^2)^{-1/2},p(1-v)(1-v^2)^{-1/2},0,0\right]$
Here it's a bit more tedious, though straightforward, to check four-momentum conservation.
To finish the analysis, let's see how the X component of the photon momentum is transformed when we boost the system. We start by adding back the powers of $c$:
$p^{boosted}_{\gamma_1x} = p\left(1+\frac{v}{c}\right)\left(1-\frac{v^2}{c^2}\right)^{-1/2}$
Using the relationship between wavelength and momentum and doing some algebra,
$\lambda^{boosted}_{\gamma_1} = h\left(\frac{h}{\lambda^{unboosted}_{\gamma_1}}\left(1+\frac{v}{c}\right)\left(1-\frac{v^2}{c^2}\right)^{-1/2}\right)^{-1}$
$\lambda^{boosted}_{\gamma_1} = \lambda^{unboosted}_{\gamma_1}\left(1+\beta\right)^{-1}\left(1-\beta^2\right)^{1/2}$
$\lambda^{boosted}_{\gamma_1} = \lambda^{unboosted}_{\gamma_1}\left(1+\beta\right)^{-1}\left(1+\beta\right)^{1/2}\left(1-\beta\right)^{1/2}$
$\displaystyle \frac{\lambda^{boosted}_{\gamma_1}}{\lambda^{unboosted}_{\gamma_1}} = \sqrt{\frac{1-\beta}{1+\beta}}$
we get the expression of the wavelength change by the relativistic Doppler effect (the difference in the sign of $\beta$ is due to the velocity sign convention).