In a response to a message on the Windows forums, a Microsoft employee confirmed that the software giant is aware of the issue. A fix for the Start menu issues is expected towards the end of the month.
In the meantime, affected users can uninstall the problematic update. This is done via the Settings menu. In the "Updates & Security" screen you need to go do "Update history" and select "Uninstall updates". Search for the KB4517389 update and hit the Uninstall button.