In order to solve the problem you need to follow these steps:
- Create a full backup of the site
- Update all outdated plugins and themes
- Flush the cache memory
- Optional: deactivate the cache memory plugin while running the steps
- Go to WPML -> Translation Management -> Filter by Header Templates
- Edit each header template in the original language -> Make a small change to the content that is not being translated -> Save the changes and update the translation
Once the steps above are finished, then the header will appear correctly translated. I followed the steps for the header on the homepage and you can see it's shown correctly translated.