Perhaps start was needed just to allow a relative directory for the icon file.

Nope, even if I have the full path to the icon file, I still needed the start.

My guess was actually because I was running from an existing cmd.exe console, so maybe there are some things you're not allowed to change on that window.

If I run the similar command from the Win+R Run menu, without the start and with full path to the icon, it also works -- again, it's creating a fresh console window rather than relying on a pre-existing window.

If I put it into a batch file, which I run perl (without the start prefix) from either the cmd.exe window or from double-clicking via explorer, then it does change the icon for either. And when the batch file is done, the window continues to use the new icon. Interesting.

Anyway, hope this helps the OP.