Here is what worked:
- Quit Messages
- Open Activity Monitor (Command-Spacebar "Activity Monitor")
- In the search field in the top right, type "dock"
- Select the row with "Dock" and click on the "X" in the top left and then click on "Quit"
This will kill the Dock application, which will restart right away and will clear the notification badge for the Messages application.