All Hallows Eve. Pagan. Stolen by Christians to replace All Saints Day, which used to be in May (and that date was taken from another pagan holiday) and was moved to the end of October/beginning of November by a Pope. It also has roots in the Celtic holiday called Samhain.
Halloween is a supplementation to All Saints Day; it doesn't replace it. I suspect you already know all this, but to be sure: starting from Jewish culture, there used to be a strong tradition in Christianity to begin celebrating Holy Days the night before. As you noted, Halloween is merely a form of "All Hallow's Eve." Which, of course, means the night before All Hallows Day (All Hallows itself being another name for All Saints). All Saints Day is still celebrated, right along side Halloween.
As for being "stolen;" if it was stolen it would have failed to serve its purpose. Christians in the 6th century would indeed attempt to replace pagan holidays with Christian ones. Pope Gregory the Great, for example, specifically wrote to St. Augustine of Canterbury to this very effect. However, the entire intent was to
replace the undesirable tradition with a desirable tradition, not to steal. To use an analogy, think of a holiday like a car. The Catholic church would come into an area and find that everyone is driving GM brand horseless carriages. The Church then shipped in a lot of Ford automobiles (or built them onsite) and gave them to the people so that they'd drive something acceptable, instead of the heathen GM
things. Calling it "stolen" doesn't accurately reflect the practice. Indeed, from some perspectives, it would have been far better if the Church had merely stolen the holidays, rather than replacing them; as it was, many times the act of replacing resulted in the original celebration being destroyed.
What's funny is that "pagan" doesn't mean anything other than "not Christian".
Actually it means something along the lines of "rural individual", coming from a time period in which Christianity was primarily in cities while non-Christian religions tended to persist in the countryside.
The concepts of witchcraft and the devil came from...pagans!
If one defines Pagan as not-specifically-Christian, then yes. However, the devil is a much-changed carry-over from Jewish tradition, and Jews are often not considered pagans by Christians. This originates in the text of Job specifically, which also happens to be one of, if not the, oldest part of the Jewish Cannon.
Perhaps you are familiar with the story? The Accuser comes before God, God says "Dude, Job there is, like, wicked faithful!," the Accuser responds with "Dude, that's messed; he's just a gold-digger. If you weren't buying him stuff, he'd drop you like brown underwear."
The Hebrew word for "the Accuser" being Hasatan, if memory serves me correctly. And the world devil coming from the Greek word "diabolos" which means the same. I have heard that this started with the Septuagint, but admittedly I haven't read that (much less in the original Greek) so I am not positive.
Since then, yes, the devil has accumulated many "pagan" trappings; sometimes being given the name Beelzebub, for example, which was a local middle east god. Certainly in Christianity he's gone from the original servant-in-good-standing-of-God to foe-of-God, which in turn foreshadowed the Christian tradition of recasting pagan gods in general as demons (the Nordic god Frey comes to mind as a notable example due to the long overlap of the Nordic religion with Christianity and the survival of many contemporary texts). But while changed, it would be improper to claim that the devil is entirely pagan.
They push their beliefs on people (evangelism, ugh!)...
While certainly I agree that their cause, means, and behavior leaves much to be desired, I would whole heartedly disagree with the sentiment that evangelism is inherently bad (or "ugh!" if you will). Though the word has been much abused in recent years, so perhaps we are thinking of different things when we see it?
At its heart, conceptually at least (as opposed to actual implementation), evangelism is altruistic. Believing that one has found something that is good, one then desires to share that goodness with others. Religious individuals are quite like Cassandra in that regard; believing that they know the future, they attempt to save others from certain destruction. They tend to be faced with the Priam's of the world... and the Christian god is certainly less hyperactive than Apollo, so these Cassandra's don't have as firm proof of their blessing and curse as the original.
If one whole heartedly believes something, and believes that such a something is good, I would certainly hope that such a person would attempt to bring others around to their way of thinking. We use evangelism for religion specifically, but the basic concept is a human one. If you believe that all humans aught be treated as free and equal, I would hope you would attempt to convert others to your way of thinking.
Attempting to force one's believe on others is, indeed, undesirable. But merely attempting to convert others to one's way of thinking is at the heart of human discourse.