What is the best way to update the name of a Service?
After renaming the .workflow file in Finder, open the file in Automator and then save the file (press ⌘ command + S). The file must be re-saved in Automator if you want the new name to appear in the menu bar and context menu.

Then, restart your computer.

By following these steps, I got my Service names to update.