If you tap the subscription option you originally purchased, Google will show an "already purchased" error and then Sync should recognize your Ultra status.

What helped me personally was: add the exact same Lemmy account which was active when you purchased Sync, and restore from its settings.

For me it was "Settings -> Other -> Restore purchases" after pressing it it was restored because I was logged in into the same Google Account on my phone as on the old phone.