Апостиль зря ставили, он совершенно не обязателен. Диплом в нашей жизни значит мало (даже если это диплом MIT - встречал и тамошних выпускников по работе, которые смутно понимали, что такое преобразование Лапласа и передаточная функция). Важны знания и навыки, и производная от этого всего - опыт.

Сначала бы Вам найти работу и получить Job Offer, а потом задумываться о бюрократической стороне дела.

В любом случае все для Вас начнется с чашки кофе и увлекательного чтения этого ресурса https://www.kmk.org/themen/anerkennung-auslaendischer-absc... Вам сюда со всеми вопросами. Они знают лучше все, чем любой из нас.

Чтобы отправить диплом на "признание", нужно приложить "прописку". Вам нужно сначала приехать

Это не так. Для признания ВО никаких регистраций не нужно. Раньше и для подтверждения звания инженера не надо было. В BW сейчас вроде (!) требуют или контракт для этого, или наличие регистрации. Но это вроде бы. Сам же делал еще не будучи и близко резидентом Германии.