I tried to calibrate it as shown in the linked video. However, the accuracy never reaches a high value and therefore this warning is always displayed on startup.
Have you tried this out in the open (trying to avoid nearby sources of magnetic interference)?
Do you use a protective case including metal or even magnets?
I just checked on my Fairphone 3, and I have no problem to get Sky Map’s accuracy reading to “high” with some calibration moves … so at least it’s not an issue of the App.
I did this in the prompt, but it shouldn’t really have to matter. I can do the calibration moves whenever I feel the compass needs improvement, and after just doing some moves it’s improved, without any prompt, mode, menu etc.