A religious friend of mine posed this question on Facebook. I'd always believed what I thought was the commonly held notion that they came from "pagan" fertility traditions. But I don't actually know the full story.
Someone posted this article in response to my friend's Facebook post. The article seems to follow the "conclusions first, then find evidence" method common to Christian apologetics, and while it looks like it contains some poor methods, I don't actually know the real answer. I hope it might be a fun topical discussion for the day today...
As already stated here, the eggs are a transcultural tradition so I'll let some real expert discuss it further.
I'll focus on the Easter rabbit since I tried and search for it myself a few years ago only to be loaded with the same type of crap OP has mentioned. I found the answer to be rather simple, though. I know this is no place for speculation, so I'll try and keep it to a minimum.
In Central Europe, Easter is still associated with Spring motifs which include seasonal flowers and animals associated with this time of the year such as hares, ducks, singing birds, chicks, and so on. So the real question would be why did the hare (or rabbit) emerge as the ultimate Easter mascot over the others in recent decades? If I'm allowed to make a guess, I'd say it has more to do with the fact it makes cuter plushies that it has with their symbolism.
As for the 'pagan fertility traditions', according to the Biblical text, Jesus's resurrection happened near or during the Jewish Passover, which also happens at the same time of the year, so the fact the Christian celebration happens at the beginning of Spring is more of a coincidence.
Ostara is a proposed goddess, and even the earliest mention we have of her should be taken with a pinch of salt. While the association between springtime and fertility is an obvious one to make and I'm in no way denying that pagan rituals may have crept into the Christian tradition, selling it as a christened pagan fest like people do Christmas (itself problematic) is, best case scenario, a bit of a lap of faith.
Edit: grammar.
I'd always believed what I thought was the commonly held notion that they came from "pagan" fertility traditions.
It is said because it's not just the Christians who paint their eggs in the spring. In the Islamic world they're known as "Novruz Eggs" and Nowruz is celebrated across different religions. In the 19th century the Russian Slavophiles believed it was an ancient "Slavic" tradition because, across Eastern Europe, the easter eggs are particularly elaborate (the "Pisanka"s) and, to orthodox Christians, Easter is (supposed to be) more important than Christmas. That's what made the jeweled "Fabergé Eggs" so popular in the Russian elite. That's why Strawinski wrote "the Rite of the Spring".
Why fertility? Well, I guess it's first thing you associate with "pagan spring cult".