Depending to your employer, he is providing you a phone and a contract. So you don't have any costs worries (this is pretty normal in Germany). The big Carriers are normally offering contracts, that includes free roaming and EU-wide usage. But expect prices up to and more than 100EUR per month. For only 1 line. Look for so called "Parntervertrag", there you can maybe combine more lines.

This 24 month locks are insane. And even if you leave Germany, you need to pay the full time. There are court rulings against cosutmers recorded. Trust me, I payed full 12 month for nothing...

Don't worry about the missing credit score. The SCHUFA is working upside down, so if you don't have a negative record, you are fine. And you can show them a copy of your last salary statement or a letter of employment. That should work.