Is it possible for a transmitter to broadcast two messages to a set of receivers at the same time using superposition coding (Non-Orthogonal Multiple Access - NOMA)?
Yes, otherwise it wouldn't be much MA, would it?
A transmitter has two messages $m_1$ and $m_2$ that wants to broadcast to a set of $n$ receivers. I think this not possible even for $n=2$. If the transmitter broadcasts $P_1m_1 + P_2m_2$ with transmit power factors $P_1$ and $P_2$, then only the receiver with higher channel gain can decode both $m_1$ and $m_2$. Is this true?
No; for example, with successive interference cancellation, you could first decode the message signal with the higher power, maybe apply the used channel coding to correct some errors, calculate what the noise-free transmit signal would have looked like, subtract it from the received signal, and then recover the other message.
That works as long as error-free recovery is possible (i.e. Shannon capacity isn't exceeded) for the stronger signal, interfered by noise and the weaker signal.
You might be interested in dirty paper coding, which essentially is the proof that you can, assuming a transmitter knows the noise it will encounter (in this case: the other message sent simultaneously), transmit without any loss of rate.