By the time you see the "Press any key" message, it is already too late to press anything.
It helps if your keyboard has an "Any" key.
Reboot Kindle
When the first character appears on the serial line, press and hold the Any key (space bar will do).
Keep it pressed until the Kindle recognizes that a key is pressed.