About my device:
Kindle Paperwhite 3 WiFi
F/W Version: 5.8.9.2
Serial (first 6): G090G1
Never been connected to the internet or registered.
On step 4, I watch the device reboot into the software update screen.
After a minute or two, the device goes to a new screen.
Software Update at the top, an exclamation below that, then a message starting about halfway down the screen:
The update was not successful.
If you need assistance, visit
www.amazon.com/devicesupport.
To resume using your Kindle, please press the power button.
At the bottom left:
UPDATE ERROR: 16
Not sure if that helps, but hopefully it does.