Hi Francois
I was two times in Berlevåg (2024 and 2025). I love Varanger! It is wild and beautiful, also Vardø.
You got already answers to your question, its an ice-road. I would like to give you some suggestions for Varanger.
If you plan to go with Hurtigruten or Havila from Vardø, first visit of course the Vardø island, cycle and walk out to the lighthouse, visit the Steilneset, Memorial to the Victims of the Witch Trials. Then on the way to Berlevåg you shoud stop in Båtsfjord. On my first visit to Berlevåg I saw Båtsfjord only from the boat and I thought, I am not missing anything, if I am not getting out of the boat. But I was wrong! The following year, when I crossed Varanger by bike, I stayed 3 nights there. The surroundings of Båtsfjord are nice for hiking with beautiful views. There is a really nice and good restaurant “Båtsfjord Brygge”, they have also rooms. https://www.batsfjordbrygge.com/en/home
From Båtsfjord you can take again the boat to Berlevåg. Berlevåg has a campsite and they have also rooms. Before cycling south from Berlevåg towards Tanabru, you should definitely visit Tanahorn. It lies 10km west of Berlevåg (not on the road to Tanabru) and can be reached by 9km cycling and approximately one-hour hike to the summit at 220 m altitude. It can be very cold and windy up there, but the view over the Barents Sea and the Tanafjord is breathtaking! https://www.komoot.com/de-de/tour/1813111067
On your way from Berlevåg to Tanabru you will find one of the most beautiful costal roads between Berlevåg and Kongsfjord! Look out for eagles!
Have fun and nice weather! Krisztina