This might help, it wouldn’t hurt or break anything:
I disabled wifi of my phone, so Homey gets forced to connect to “the cloud” per mobile internet data connection;
Next, I could connect Homey to Google Home right away.
(On wifi I sometimes had to start the connect procedure 20+ times until it finally succeeded).