See Vector Spherical Harmonics and total angular momentum.
What makes this question hard to get our heads around? When we think about angular momentum and optical fields we typically think about paraxial beams of light. Such beams have spin angular momentum (SAM) due to local rotation of their polarization vector and orbital angular momentum (OAM) if their spatial pattern is that of a higher order Laguerre Gaussian mode. The spatial profile of these beams is essentially unchanged as a function of distance along the propagation axis. This symmetry along the propagation axis makes it very easy to see where the SAM and where the OAM respectively live. Furthermore, the nature of the angular momentum doesn't change along the beam. Also this intuition with beams builds upon or intuition with plane waves which have constant linear momentum throughout all space.
However, the question we consider here of an atom emitting light into all direction in space is different. We can't take our intuition from beams along anymore.
Without getting into too much detail.. instead of taking plane waves with different polarizations as our basis for vector functions which span the space of all possible vector electric or magnetic fields, we can use the basis of Vector Spherical Harmonics. Of course there are change of basis formulas relating these two bases. The dipole radiation pattern I illustrated in What is the radiation pattern for an electric dipole rotating in the horizontal plane? is an example of a vector spherical harmonic.
In Vector Spherical Harmonics and total angular momentum it is explained that vector spherical harmonics have a fixed value for total angular momentum $\boldsymbol{J}$ but are superpositions of orbital optical, $\boldsymbol{L}$, and spin optical, $\boldsymbol{S}$ angular momentum.
This squares with our intuition about the dipole radiation pattern depicted above. We can see that in parts of the pattern (top and bottom) we see circularly polarized light which we know carries SAM, but in other parts (horizontal plane) we see linearly polarized light that rotates as a function of azimuthal angle. We know this pattern carries OAM.
This superposition of differing states of $\boldsymbol{L}$ and $\boldsymbol{S}$ is the same as for the case of angular momentum addition in an atom. The states with well defined values for $J_z$ are superpositions of states with well defined values of $L_z$ and $S_z$. And so it is for the dipole radiation pattern.
So how does this come back to the paradox raised in the original question. The answer is that the atom begins with $\hbar$ of angular momentum in the $z$ direction. When it decays we know it gives up all of its angular momentum. It gives up its angular momentum to a state of light which has the mode pattern depicted above. This state of light has both spin and orbital angular momentum, but it has a well defined total angular momentum of $\hbar$. The intuition that has failed us and made us think there is a paradox was the intuition that "horizontally polarized light in the $xy$ plane can't carry the angular momentum in the $z$ direction as needed.
The problem with this intuition is that one must consider the overall state of the light field over all space to determine its angular momentum.
Where I got tripped up was in considering a detector placed along the $x$ axis. If a photon is detected we know it is linearly polarized in the so it can't carry optical spin angular momentum in the $z$ direction. Where then is the angular momentum after detection and subsequent collapse of the quantum state? The answer is this. Because the detector has finite spatial extent there are a range of plane waves consistent with causing the detector to click. Each of these plane waves is correlated with the atom recoiling in the opposite direction. However, because of the orbital angular momentum of light, each of these plane waves has a slightly different phase. This phase gets imprinted onto the recoiling atomic plane wave. The sum of the atomic recoiling plane waves will then have some circulation to it, that is, external orbital angular momentum of the center of mass of the atom. So, after detection by such a detector, the atom will be found to have external orbital angular momentum.
The story I just told above is a tricky story to tell because the detector I'm choosing is not very commensurate with the other useful bases for the problem, so a lot of change of bases need to be mentally jumped through.
Note that prior to detection, all of the angular momentum is in the light. However, after detection, the angular momentum is found to be in the atom. What gives? The answer is that the light and atom are entangled. And they're entangled in such a way that the total orbital angular momentum of the light is $\hbar$, and the total orbital angular momentum of the atom is 0. However, by detecting as I described above, you can project the joint system into a state where the atom has all of the orbital angular momentum.
