And it depends on existing verified pages (you get verified by.. having two other verified social network accounts). If you can pay to get one of those, that's half of the job done for 20$.
Telegram Premium does not at all depend on your other social profiles, it’s $5/mo. Maybe they have a separate verification feature? (Edit: yep https://telegram.org/verify )
Telegram premium adds a star to your name rather than a check mark. It only signals you paid for premium.