Telegram app seems not to have a version for Apple Watch in the app store currently. I do not know if it had a previous version … and somehow it got removed from your watches … seems weird.
I have been using Telegram on my iPad, iPhone and Apple Watch for a number of years now and it has worked perfectly. It's only recently that I have noticed it missing.
I think if it was because it's Russian, I think they would have removed it from the iPhone and iPad too.
It's been missing for at least a couple of months. Some people on reddit say the watchOS app is being rejected by the app store, which is why it's not available.