I think the answer may be Yes, and Yes.
That is - yes, it is probably illegal. Yes, you can probably bring some as a souvenir. Yes, those answers contradict each other.
Coca leaf is banned, under the narcotics laws, in most every country except a very few, including Europe and USA in the list of countires where it is banned (as mentioned in Mark Mayo's well researched answer). Coca leaf was banned, it looks like, specifically to interfere with people chewing the leaf as a habit. Of course, the law doesn't care to specify a difference between leaves intended for tea purposes, rather than coca-chewing purposes, since the leaves themselves will be the same - but that emphasis on the chewing as the reason for the ban might be the reason why some sites claim teabags would be let through, while loose-leaf might not be.
On the other hand, coca leaf tea is available for sale in the US (I realize your question was Europe, but the same set of laws are in play). I saw a few listings, on amazon and ebay, so someone is importing it while under those laws, in salable quantities. I think in practice the restriction is working like it has to do with those authorized to import and distribute, rather than a blanket ban. We have 1690's anecdote that some customs will allow it through. It may be that the tea is low enough on the priority list for individual customs people, that it isn't reliably recognized as banned. It might be that the presence of legitimate sources for the tea, obscures whether your souvenir packet was from one of those legit sources. It may also have to do with the totally legit cocoa tea (cocoa nibs are becoming popular additions to some tea mixes) and whether the legitimacy of the two might be unclear in some customs officer's minds.
So, if you pick up a small quantity of mate de coca, you have a fair chance of keeping it, and another fair chance (if it is caught) that it will simply be discarded, with no extra penalty to you. A grocery store box of teabags looks like something a person might not have thought about - even if you really did - so they will probably treat it like a mistake unless you've got a really suspicious quantity or other red flags. Obviously, your chances are better with a small quantity obviously intended for personal use rather than resalable quantities (or, hoarding for an extended timeline of use quantities, which can look the same). Your chances are considerably better with neatly labeled, grocery-store-sealed boxes of teabags rather than a quantity of loose leaf or raw coca leaves in a hand-labeled bag.