James_Neave: I found a solution to this here:
https://support.gog.com/hc/en-us/articles/213520069-Settlers-3-Ultimate-Collection?product=gog

Under "Settlers® 3: Ultimate Collection - Game asks for CD-Key in singleplayer mode"

If you are using GOG GALAXY, select the game and click the customization icon (next to PLAY):
→Manage installation
→Verify/Repair

This fixed the CD key issue for me after I had fixed the not-starting issue by using the offline installer