I have solved my problem on my own:
The correct number format for Link2Voip is 011 49 ...
Regarding the CLI see
https://www.link2voip.com/faq/#faq59
I have created the respective SIP users and it works.
To prevent the 603 error I had to add my IP address to the table shown above ("SIP Outbound Trusted IPs").
With my softphone I can now use Link2Voip via Voxalot and it is showing the correct CLI.
With my ATA (AVM Fritz!Box 7270, see signature) I'm still getting the 603 errors, so that this issue is only partly solved. Also updating my dynamic IP address on the Link2Voip homepage is not really an option for me... :-(