I believe the program icon on the Start menu is also a shortcut, so you can right-click it and use the Properties dialog just as you did with the desktop shortcut.

For a pinned Taskbar icon, if you right-click it, toward the bottom there should be a "Mozilla Firefox" item on the right. Right-click that and you should be able to access the Properties dialog. Alternately, you could unpin it temporarily and repin it later.

Does that work?

Sometimes the easy solution is to try again what one thinks they've already tried. Such was true for the icon Properties change to the Start Menu item.

Thank you jscher, and thanks for the guidance to change the pinned Taskbar item. Both worked.

Similar to question 1153574, I got the icon back by refreshing windows icon cache:

Try to rebuild the icon cache (IconCache.db).

1. Open windows explorer (Win+E) and navigate to %LocalAppData%
2. Ensure hidden files are visible, and delete IconCache.db
3. Open the Task Manager (Shift+Ctrl+ESC)
4. In the Process tab, right-click on the Explorer.exe process and select End Process.
5. Start a new explorer.exe process via "File > New Task (Run)" to get the desktop and Taskbar back, and regenerate the icon cache.

Note that IconCache.db is a hidden file, so make sure you can see hidden files.