This info might be useful for developers for a bug fix:
I have had problems connecting S6 to Express for quite some time.
Earlier this week, when charging the watch, suddenly the connection was made. This happened when the Garmin Servers where down.
When the server where back up again, I again could not connect to Express.
Switching WiFi off and back on again has resolved the issue permanently it seems.