Sleep paralysis combined with hypnagogia (and/or hypnopompia, depending on how semantic you want to be) is the origin of the various myths surrounding this phenomenon. It's not just the sleep paralysis itself that spurs these legends. If all you experienced was the paralysis aspect, then you didn't really get the "full effect" of the experience.
The altered mental state and auditory and visual hallucinations are what make it truly terrifying, in conjunction with the paralysis and inability to easily wake from the state. Emotional distortion, sense of doom, a sense of a presence in the room with you (which often feels evil and malevolent), a sense of pressure/pressing on your chest (thought to be a simple perceptual oddity related to sleep paralysis autonomous breathing while conscious), auditory hallucinations (often whispers or voices), and even full-fledged visual hallucinations, all while lying in your bed paralyzed, is quite scary. I've experienced it many times with effects up to and including visual hallucinations in my peripheral vision, and I can see why people attribute this to supernatural or extraterrestrial causes. Particularly since it can be a reoccurring thing happening many times a night or many nights in a row.
The most important distinction is that it does NOT feel like a "dream state". I don't know enough about the science to know how closely this state physiologically resembles a dreaming brain, but I can definitely say that perceptually it feels like no dream you have ever had. The feelings and hallucinations, in conjunction with the paralysis, is a completely lucid, conscious experience. When you manage to wake from it or snap out of it, it in no way resembles the usual dream sensation that you typically feel after even the most vivid of nightmares. If your eyes are open and you have a view of something useful in the room, you can verify your experience against external stimuli... the time on the alarm clock, noises outside, animals/pets inside moving around, etc. All of which can be correlated to reality if you wake up shortly after, though of course arguably all these perceptual things could be incorporated into a dream, but at that point you'd be arguing semantics. Suffice to say I have had many dreams and nightmares, some extremely vivid, even some lucid, but none have ever come remotely close to the conscious "real" feeling of one of these episodes. I have no doubt that the majority of UFO abduction reports are caused by this, and as I can attest to how real it feels I can sympathize with those who are firmly convinced that the hallucinations they experienced were a real event for them.
For me it was terrifying at first, but after 6 or 7 events and some research, I finally figured out how to wake myself from this state "on demand", or nearly enough, which removed most of the panic and took the edge off. The experiences can still be frightening and filled with many scary perceptual phenomena, but knowing what it is and how to get out of it helps put it back into the realm of a typical nightmare.
For those who may happen to find themselves in this state some night, the most important thing I've found is that it is nearly impossible to "fight" your way out of it into wakefulness (though I once managed it when convinced that the "evil presence" was attacking my wife). Fighting against it just tends to make it worse and increase your sense of panic. It is far more effective to recognize what is happening and then try and relax. By calming yourself you can usually slip back into a fully asleep state, from which I almost inevitably come fully awake within about 10 minutes (as verified numerous times by the last time I remember seeing on the clock, and the time on the clock when I then snap awake, though perceptually it generally feels instantaneous). Most frustrating is when you repeatedly slip into this state over and over in a night. Usually a change in position (rolling over, etc.) is sufficient to prevent that, but occasionally I've had to come to full alertness (10 or 20 minutes awake in the light) to keep from repeatedly slipping back into the same state.