What you're desribing sounds like a mixture of potentially normal sleep related phenomenon, plus headaches. Also, you need to at least think about narcolepsy (
http://en.wikipedia.org/wiki/Narcoleptic), seizures, psychiatric problems like schizophrenia, just plain nightmares, or PTSD. I'd be most curious about narcolepsy.
1) The paralysis is called "sleep paralysis," and it may be either hypnopompic or hypnogogic. It should properly be a full paralysis, save for preserved diaphragm and extraocular muscle activity. It should pass spontaneously within seconds to minutes. The hallucinations may be occurring during the paralysis. The SP may be seen in the setting of narcolepsy, fragmented sleep (like medical residents/college students, or occur in isolation of other symptoms). It is not unusual to feel that something heavy is on your chest during these spells, and it is also not unusual to sense a dark/evil presence in the room during these events. Many ancient cultures have described this, and it has given rise to myths about witches or "mares" riding on people's chests at night. If combined with hallucinations, the effect can be quite terrifying for the uninitiated. People may also have kinetic sensation (falling, or even rising off the bed a la alien abduction stories) with this.
This is where the term "night-mare" orginally came from. Note the interesting pieces of artwork in the article:
http://en.wikipedia.org/wiki/Sleep_Paralysis
2) The hallucinations all depend on context. You say that these are only during sleep and are not before or after falling asleep or waking up? They may simply be dreams, but they sound more like sleep hallucinosis from what you've typed. If they are during the day (and not related to sleep), then they may or may not be related to narcolepsy. Olfactory hallucinations are rare, and auditory ones should be thoroughly questioned so you rule out psychiatric disease.
Typically with narcolepsy and with very fragmented sleep in college kids etc you have hypnopompic or hypnogogic hallucinations. They are most often visual. You see them with your eyes open. Usually phosphenes, shadows, shapes, scenes (like looking through a window into a meadow), silhouettes of people/men standing at the foot of your bed, ghosts, demons, animals like spiders and bats and the like.
http://en.wikipedia.org/wiki/Hypnagogia More rarely, you can have kinetic, auditory, tactile, or olfactory hallucinations. Also, you need to be sure that your patient is not just describing dreams...which are a separate entity altogether.
3) Be sure to ask about cataplexy.
http://en.wikipedia.org/wiki/Cataplexy
4) Again, it sounds like the guy may have anything along a gamut from psychiatric disease, very fragmented sleep only, narcolepsy, or even seizures. What you are describing sounds most consistent with narcolepsy, or at the very least, extremely fragmented sleep with interspersed sleep hallucinosis and sleep paralysis.
I'd recommend an EEG (remember the olfactory hallucinations, and also are any of the hallucinations stereotyped?), possibly a psych consult (depending on those voices, possibility of nightmares, and possibility of PTSD), screen his medications (anticholinergics or antidepressants?), give him a full neuro exam, and take a thorough history of these hallucinations and sleep patterns.
He likely will need a PSG (with MSLT and urine drug screen) to check for OSA, nocturnal seizures, other disturbances of sleep, and to rule out narcolepsy.