Found a solution:
- Uninstall ALL apps on the Gear s visible as "installed"
- Uninstall gear manager on the phone
- Install gear manager again on the phone
- Pair phone with gear s
- Re-install apps - Opera will now install as well
It's like changing all the tires of your car while only 1 needs a bit of air, but it works...