So I deleted my device from the garmin connect app,OK, I tried that too just now on my iPad, and I did have trouble pairing my Forerunner‑235 with the Garmin Connect Mobile app anew. It took several attempts before the watch gave me a six-digit passcode to enter in the app to complete the pairing operation.
and when I now try to pair it just says "waiting for app" on my watch and that device cannot be found on the phone.The only place I've seen “Waiting for app” on my watch is in the Controls widget, which has nothing to do with pairing; and, no, I didn't see that message in spite of having trouble pairing my watch with my iPad earlier.
Are you trying to pair, or are you just trying to connect after having previously paired with Garmin device with your iPhone? Those are logically separate events, so be clear.