Yes, magic was feared in Europe before Christianity became the dominant religion. That's the quick and easy answer, but there's much more to it once we start getting into the detail. The two biggest (and most interesting I think) sub-questions here are:
what kinds of magic were people afraid of?
who practiced this magic, and were they ever 'hunted'?
I'm not going to deal with the question of "what is magic?" in too much detail - it's a huge question, and an unresolved debate that stretches across a number of academic fields. Far too much for a Reddit post!
My expertise is on Roman magic, so that's where I'll be concentrating, but the answer would likely be different if you shifted the focus to other social and cultural contexts. I should also state right from the start that evidence for attitudes to magic in the Roman world is fairly sparse, and is very much coloured by social and cultural prejudices. All of the authors of the surviving literary texts that discuss magic were wealthy, free males, based in or around the city of Rome. This presents a very specific view of ancient magical practices - something I'll come on to discuss in more detail later. I have also talked about it in another answer here, which you might also find interesting.
Question 1 first. As a start, let's look at a quote from Pliny the Elder, writing in the mid-1st century AD:
Defigi quidem diris precationibus nemo non metuit
there is nobody who does not fear to be bound by dreadful curses (HN 28.4.19).
Now, that seems like a pretty clear answer to your question: Pliny says that everyone is scared of being bound by 'dreadful curses.' But what kind of magic is he talking about? Odds are he means curse tablets and binding spells, which were an incredibly common phenomena in the Graeco-Roman world. These were written on small pieces of lead, and were used to control the actions or well-being of other people or animals. By way of an example, here's one from London (Roman Inscriptions of Britain no. 7, see here for more info), possibly dated around the same time as Pliny was writing:
I curse (defigo) Tretia Maria and her life and mind and memory and liver and lungs mixed up together, and her words, thoughts and memory; thus may she be unable to speak what things are concealed, nor be able to love...
It uses the same word for 'binding' (the Latin verb defigo), which is common on these kinds of spells, hence why I think this is what Pliny is talking about. Curses like this have been found from across the Roman empire, and were usual used to attack wrong-doers (especially thieves) or rivals (in love, law courts, sporting competition or business). They may have been produced with the help of ritual specialists, but I think in most cases the curses were made directly by those who were involved - the love rivals, the parties involved in the trial, the victims of crime etc.
Cursing was part of the category of magical practice that was most fearful to the elite male authors of our literary texts: "love magic", or curses, potions, charms and other rituals that attempted to influence sexual and romantic relationships. They probably wouldn't have admitted it, but for Roman elite men, their dominance in sexual relationships was one of the most significant elements of their social and cultural privilege. Total control over when, where and with whom they had sex was a core part of their identity, and to suggest there was any compromise in that was a serious thing. They were paranoid about any subordinate group (women, slaves, foreigners etc) challenging this control, especially through nefarious or supernatural means. It's worth remembering that elite men were also in total control of the official religious system, as the priests and magistrates who communicated with the gods on the community's behalf. Love magic challenged elite male dominance in two ways then - it subverted their control of both their sexual and religious lives. There's a fabulous passage in a poem by Ovid that sums this up really nicely (Amores 3.7.27-36, you can read the whole poem here). The poem is a complaint about not being able to perform for his lover, and one of the things he thinks might be causing his erectile dysfunction is malicious magic:
Has some Thessalian poison weakened my cursed body?
Do charms and herbs hurt my poor self now,
some witch transfixes my name in scarlet wax
and sticks fine needles right into my liver?
Charms turn the stricken wheat to barren grasses,
charms stop the stricken waters at their source,
through incantations oaks drop acorns, vines their grapes,
and the apples fall down without being shaken.
Why shouldn’t I be stopped, and my vigour numbed
by magic arts, my body by that made unable to endure?
In Roman literature, the trope of evil old women attacking the sexual abilities of young men was very common. As I've said, I think this is a symptom of the paranoia in elite men that those they considered inferior might find ways to challenge the social order. Whether other groups of people would have found these kinds of practices so fearful is a really interesting question, and not one we can easily answer. However, I think the widespread finds of curses, amulets, charms and other magical objects across the Roman world suggests that below the level of the aristocracy people held a much more pragmatic attitude towards magical practice, especially rituals that addressed things like agricultural production and personal safety. At this level of society, anything that could protect livelihoods from the difficult conditions most people lived in would have been welcome. Sometimes that would have been rituals and practices that the elite recognised as 'acceptable' religion, but at other times it seems very likely that they would have resorted to rituals that the elite would have found much more problematic.
On to question 2: who practiced this stuff, and where they hunted?
Outside of literature written by the likes of Ovid and Pliny, the evidence for real magical practitioners is incredibly thin. The curses I began with are usually anonymous, with the only names being the victims. Scholars have usually followed the prejudices of the elite male writers, and have assumed that there really were witch-type figures practicing this kind of magic in the Roman world. Their domain seems to have been herb-lore, potions and other charms: the kind of rituals and practices that seamlessly blend religion, magic, medicine and science that should make us moderns question where and how we make distinctions between those categories. Roman law might give some hints too. I quoted this section of a legal text in the other post I linked above, but it's worth looking at here too. It's written by Paulus (Opinions 5.23.14-19), a Roman jurist writing in the second century AD, talking about the lex Cornelia sicariis et veneficis, first passed around 82 BC, but probably added to later:
Those who administer a potion to cause an abortion or as an aphrodisiac, even if they do not act maliciously, nevertheless because their action is a bad example, those of inferior rank are sentenced to the mines, and those of superior rank are banished to an island, after part of their property has been confiscated. But if a woman or a man dies from the potion, they receive the supreme penalty. Those who perform or have performed for them impious or nocturnal rites for the purpose of enchanting, bewitching or binding someone, are either crucified or thrown to the beasts. Those who sacrifice human beings or take auspices with human blood or pollute a shrine or temple, are thrown to the beasts or, if they are of superior rank, executed. Those who are knowledgeable in the art of magic are to receive the supreme penalty, that is, to be thrown to the beasts or crucified. The magicians themselves are burnt alive. No one may possess books on the art of magic; and those found in possession have their property confiscated and their books burnt in public; they are deported to an island or, if of inferior rank, executed. Not only the practices of this art, but also the knowledge of it, is prohibited. If someone dies from a drug which was administered for their health or as a cure, the person who administered it is, if of superior rank, banished to an island or, if of inferior rank, executed.
It doesn't tell us exactly who was practicing these magical rituals, but certainly helps answer the 'hunting' aspect of your question. Certain kinds of magical ritual were clearly illegal - again we see love magic, as well as other forms of cursing, poisoning and so on. Importantly, even knowing about this stuff, or even owning books about it was illegal. Again, I think we're seeing the fear of challenges to elite power here.
Quite how often people were prosecuted under these laws is uncertain. We don't have that kind of detailed record from the Roman world, so ultimately we'll never know. However, there is very good evidence that various magical practitioners, especially astrologers, were expelled from Rome on certain occasions. As an illustrative example, the emperor Tiberius expelled "astrologers and magicians" from Italy after uncovering a conspiracy against him that had potentially had some magical or supernatural elements (see Tacitus, Annals 2.27-32 for the full story). I suppose this is the closest thing the Roman world had to witch-hunts before the advent of Christianity.