Запятая не требуется, поскольку части предложения объединены вопросительной интонацией.

Приложения неоднородны: кавалер ордена и генерал-лейтенант — это звания, а генерал-губернатор — должность. По правилам при сочетании однородных и неоднородных приложений соответственно расставляются и знаки препинания, однако в качестве примера обычно приводится перечень из двух-трех однородных и одного неоднородного приложения (заслуженный мастер спорта, олимпийская чемпионка, двукратная обладательница Кубка мира студентка института физкультуры NN). Три неоднословных приложения в родительном падеже, не разделенные запятыми, неудобны для восприятия, но для такого случая правила нам никаких рекомендаций не дают. Если контекст позволит, предлагаем поставить приложения после определяемого слова, такие приложения разделяются запятыми: ...улица была названа в честь И. И. Иванова — георгиевского кавалера, приамурского генерал-губернатора, генерал-лейтенанта. Если перестроить предложение нельзя, то полагаем, что запятые лучше поставить для облегчения восприятия. 

Обратите внимание: сочетания георгиевский кавалер, приамурский генерал-губернатор пишутся со строчной буквы. 

Верно: Магазин переехал и находится по адресу: улица Вокзальная, 1.

Написание сложных прилагательных в подобных названиях нередко вызывает затруднения, т. к. пишутся эти прилагательное неединообразно: одни из них принято писать слитно, другие – через дефис. Многое здесь обусловлено традицией, при этом орфографическое оформление одних и тех же названий в разных городах может различаться. Например, в Москве есть улица Маломосковская, но в Вашем городе может быть принято дефисное написание этого названия. Лучше всего уточнить, как писать эти названия, в городской администрации.

Если же пытаться ответить на вопрос, как должны быть написаны такие названия (без учета сложившейся традиции), то, видимо, следует вспомнить общие правила правописания сложных прилагательных. Слитно пишутся прилагательные, образованные из основ слов, отношение между которыми носит подчинительный характер (железнодорожный от железная дорога, станкостроительный от строить станки и т. д.). Пишутся через дефис прилагательные, образованные из основ слов, обозначающих равноправные понятия (англо-русский от английский и русский, научно-технический от наука и техника и т. д.). По общему правилу прилагательные, образованные от сочетаний пешие стрельцы, конные стрельцы (подчинение), должны писаться слитно: пешестрелецкий, коннострелецкий. Первые части сложных слов мало... и средне... по общему правилу тоже пишутся слитно. Поэтому более логично слитное написание всех перечисленных Вами названий. Но это, повторяем, без учета сложившейся в городе традиции, а ее, конечно же, надо учитывать.

Литера пишется слитно с последней цифрой номера: улица Калинина, 41б. Предпочтительна строчная буква, прописная допускается, если строчную букву можно спутать с цифрой.