Что делать, и законно ли действие сотрудника паспортного стола?

Добрый день, Виталий!

В соответствии с п.п. 12, 13 раздела II Постановления Правительства РФ N 828 «Об утверждении Положения о паспорте гражданина Российской Федерации, образца бланка и описания паспорта гражданина Российской Федерации» замена паспорта при достижении возраста 45 лет производится  при предоставлении следующих документов:

паспорт, подлежащий замене;
две личные фотографии размером 35 x 45 мм;
документы, подтверждающие указанные в пункте 12 настоящего Положения основания для замены паспорта.

То есть третьим документом, который нужно предоставить, является в Вашем случае документ, подтверждающий, что Вам исполнилось 45 лет. Вероятно, поэтому от Вас требуют свидетельство о рождении.

При этом Верховный Суд Российской Федерации сделал вывод, что гражданин обязан представлять в территориальный орган МВД свидетельство о рождении только в случае получения нового паспорта, но не при его замене (решение ВС РФ от 20 марта 2017 г. № АКПИ17-78). 

Попробуйте обратиться непосредственно в УФМС (миграционную службу), которая и выдает паспорт (паспортный стол при управляющей компании является просто посредником), либо в МФЦ (тоже посредник, который передаст документы в УФМС). 

Если при обращении непосредственно в УФМС от инспектора — сотрудника полиции получите отказ, тогда следует написать жалобу на имя начальника УФМС.

Что касается расхождения между паспортом и свидетельством о рождении в буквах «е» и «ё», к сожалению, их можно устранить только путем обращения в суд с заявлением об установлении юридически значимого факта.