It was first believed that he got lost in a storm and had died in the cold weather.

这个句子出现了三个动词：believe, get, die。

believed 发生最晚，用了一般过去时。从意思上看，另外两个动作早于 believed 发生，应使用过去完成时：had got lost 和 had died。—— and 连接两个并列的动作，时态上不需要分先后，都用同一个时态即可。改为：

It was first believed that he had got lost in a storm and （had）died in the cold weather.