I found the solution for this for our organization. The admin user had Global admin privileges and was still getting the message. The error is not descriptive; the actual issue was we did not have a sufficient license to use the service. You need Azure Active Directory P1 or P2 to enable this service and get rid of this error.
Upgrading to P1 or P2 is incredibly convoluted as most MS licensing is. We have Azure AD as a result of having O365 Business Basic licenses, which allows us to login to the Azure Portal: https://portal.azure.com but to add the P1 or P2 license you need to log into the 365 admin portal: https://admin.microsoft.com/AdminPortal and navigate to Billing - Purchase Services. Search for "Azure" and you can then purchase P1 or P2. There is a P2 trial available for 100 users that we signed up for, then go back to the Azure portal and the On-Premises Integration no longer shows the "Insufficient Privileges" message.
Requirements for password write back in a hybrid environment are listed here: https://learn.microsoft.com/en-us/azure/active-directory/authentication/tutorial-enable-sspr-writeback#prerequisites
How to sign up for premium licenses is listed here: https://learn.microsoft.com/en-us/azure/active-directory/fundamentals/active-directory-get-started-premium