I heard from an old Lithuanian/Polish Jew (frum from Lithuania/Poland). He says that he had a custom to eat colored eggs in his shtetl, and everyone did it.
Is this custom documented anywhere, and does anyone mention it?
Despite it's apparent similarity to pagan practices dating back thousands of years, this custom exists in some communities (particularly among Lubavitchers and some other Chassidic groups) and dates back at least several decades. Similar customs (such as eating colored eggs on Purim) existed in Jewish communities in Afghanistan and Yemen, and women in Tunisia would write messages on eggs for Lag Ba'omer. These customs date back at least several decades, too.
The customs of these various kehillos may share a common origin, but how much farther back these various customs extend may be a matter of speculation. Interestingly, the earliest known pagan custom originated in Persia around the time of Purim, and may therefore have been adapted from a Jewish custom for Purim.