SOLVED:
It appears that the new version of Office (16/O365) is missing some entries that the ICloud for Windows is looking for to know whether to show the Contacts/Calendar option or not.
Close Outlook
Open the Registry Editor
Navigate to: HKLM\SOFTWARE\WOW6432Node\Microsoft\Windows\CurrentVersion\App Paths\OUTLOOK.EXE
Double-click (Default)
Enter the path to your Outlook.exe: C:\Program Files\Microsoft Office\root\Office16\outlook.exe
Reopen the iCloud for Windows Settings and select Contact and Calendar option. When it completes the configuration, open up Outlook
You should now have it syncing like it was before!
Cbeers