So I contacted Amazon again. This time, it took longer time to explain them that it is not about Software Update, but certificates. The conversation ended up with the 'official' explanation that 'Kindle 5 Non-Touch is a legacy device that Amazon does not support in full', so there should be no other changes expected to system files whatsoever.
OK. Meanwhile I found by accident
THIS.
On the first page of our thread
arifunke tried to change the certificates manually.
I pulled Kindle's certificates file /etc/ssl/certs/ca-certificates.crt, opened it and followed the
website at the top. The files there are in .pem format, however, from inside their structure looks the same as in Kindle's .cert files, with BEGIN-END notation.
Now question: how do we pull all these pieces of information together to update Kindle's certificates?