Подскажите, если в Германии я переехал с одной улицы на другую в пределах города. Должен ли я уведомить орган регистрации автомобилей об этом? Как? Не могу найти эту процедуру.

Насколько понимаю, да. Обратитесь в свой Zulassungsstelle.

При переезде в рамках одного города достаточно регистрации по месту жительства. Kfz-Zulassungsstelle получит эту информацию автоматически. Не уверен, что это работает во всех городах. Лучше спросить в ратуше.