I have a solution Support told me to double check, whether my secure phone number is from the country, my Apple ID is registered in. When I changed my number to one from my country, it worked.

Make sure, a phone number from the country your AppleId is registered in is connected with your ID.