Although switching from Chrome to Firefox as mentioned in Problem: Office 365 Connector setup failes when "Access the application to UCS Authorize", the connection results in a 401 Forbidden error. Or do I have to go through the whole wizard using Firefox?
Okay, I found the following: UCS tries to complete the configuration using the user I am logged in with at Office 365. But my personal user account was unprivileged to complete the process. After adding it to Administrators and Domain Admins it worked.