Trouble pairing Fenix 7s with iPhone 16 Pro

I've had my Fenix 7s for several years now, paired successfully with an iPhone 14 Pro and iPhone 6s, but I can't get it to pair with my new iPhone 16 Pro.

What works:

  • Pairing Fenix 7s with iPhone 14 Pro
  • Pairing Fenix 7s with iPhone 6s
  • Pairing other bluetooth devices with iPhone 16 Pro

What does not work:

  • Pairing Fenix 7s with iPhone 16 Pro via Settings => Bluetooth
    • Fenix 7s does not appear in the list of available devices
  • Pairing Fenix 7s with iPhone 16 Pro via Garmin Connect app
    • Click the blue + button
    • on "Select Your Device" screen select "Browse all compatible devices"
    • on "Compatible Devices" screen select "Fenix", then "fenix 7S"
    • next screen shows "Pairing Your fenix 7S Device" with "Searching ..."
      • No devices are shown
    • After a while the "Open Troubleshooting" button appears

Troubleshooting I have already tried:

  • Powering off watch, powering back on watch
  • Un-pairing the watch from the old device (iPhone 6s)
  • Taking the watch to "Connectivity" -> "Phone" screen
  • Taking the watch to "Connectivity" -> "Phone" -> "Pair Phone" screen
  • scanning the QR code on the "Pair Phone" screen from my phone
  • Powering off phone, powering back on phone
  • Deleting Connect app, powering off phone, powering back on phone, re-installing Connect app
  • Re-trying to pair with old phone
    • pairing with old phone still works fine
  • Testing other bluetooth devices with iPhone 16 Pro
    • all other bluetooth devices work fine
  • Checked that I am on the latest version of all available software:
    • Fenix 7S software version 18.14 (f40ace5)
    • iOS version 18.0
    • Garmin Connect app version 5.5

Because my phone works with other bluetooth devices, and my watch works with other phones, I thought maybe there was an incompatibility between Fenix 7 series and iOS 18, or with iPhone 16 bluetooth stack. But I can't find any reports on the web for this.

Has anybody else successfully paired their Fenix 7 series watch with an iPhone 16 Pro? Or with any iPhone running iOS 18?