I had this exact same issue and I am SHOCKED that Amazon don't make this a more obvious path to follow!
I had to find this out via a random article on how older Kindles are being disconnected from the internet. And if your Kindle failed to update before March 2016, it would be disconnectedfrom the internet and thus unable to update itself. But there IS a solution. It's time consuming but possible!
(Article here: https://www.theverge.com/2016/3/20/11271... )
Okay, so... head to Amazon Device Software Updates. ( https://www.amazon.com/gp/help/customer/...vg[p]11035921[t]w[r]ifixit.com/Answers[d]M&nodeId=200529680 )
Select Kindle E-readers
Find your Kindle ( https://www.amazon.com/gp/help/customer/... )
If you have missed several updates, you will have to upload each update ONE at a time.
You will have to download the updates on to a laptop or pc.
Then connect the Kindle via a cable, and drag and drop the FIRST update that you are missing from your downloads folder to the Kindle folder.
Then eject your Kindle and remove the cable.
Go to settings menu, press settings again, and then select Update Kindle. Leave it alone until the update is finished.
Then plug the Kindle back into your PC. Drag and drop the next update in series from downloads to the Kindle folder. Eject, unplug, update Kindle in Settings.
Repeat this process until you are on the latest update.
Manually Update a Kindle: https://www.amazon.com/gp/help/customer/...
Important info on previous software updates: https://www.amazon.com/gp/help/customer/...
Please let me know if this helped you!?
It worked for my 2011 4th Gen Paperwhite :)