Hm… Another thing that could be tried is to move the builder over to a different region, like ams or cdg:
https://community.fly.io/t/region-cannot-host-your-machine-fra/23071/31
(These days, you might also need --recreate-builder, on that command line.)