Most likely, a Hetzner storage box is going to be so slow you will regret it. I would just bite the bullet and upgrade the storage on Contabo.

Storage in the cloud is expensive, there’s just no way around it.