If you can't find the app listed in My Watch/Notifications, or scroll down for the other list of apps under My Watch there seem to be 2 possibilities,
1. Something wrong in the phone or watch setup.
- Check software versions in the phone and watch. You should have iOS 11.4.1 and WatchOS 4.3.2.
- Check the App Store for updates, the recent iOS and WatchOS might need a later version of app.
- Try rebooting both your iPhone and your Apple Watch. If that doesn't work you could try uninstalling the app then download again and reinstall.
2. Contact Telegram support for their suggestions. It may be something simple, or you might have found a bug!