Обязан ли он покинуть пределы РФ?

Нет, в вашей ситуации уезжать не обязательно. Я поясню, в чём тут дело: обязанность покинуть РФ возникает не из факта просрочки регистрации, а из текста постановления, которое вынесли после нарушения.
Ключевой момент: если в постановлении написано только о назначении административного штрафа (без слов «административное выдворение» или «обязать покинуть территорию Российской Федерации»), то обязанности выезжать нет. В этом случае после оплаты штрафа можно остаться в России — например, оформить новую регистрацию или другие законные основания для пребывания. 
Поэтому первым делом возьмите копию постановления и внимательно прочитайте его. Ищите именно формулировки про выдворение. 
А если в постановлении есть выдворение?
Тогда обязанность выехать появляется. Обычно в таких случаях назначают контролируемый самостоятельный выезд: вам дают срок (часто 5 дней), чтобы самостоятельно покинуть страну. Если не успеть — последует принудительное выдворение. 
Ещё один нюанс
Иногда суд при назначении наказания учитывает личные обстоятельства. Например, если у человека в России семья (супруг/а — гражданин РФ), дети, устойчивые связи, суд с большей вероятностью ограничится штрафом без выдворения. Это не отменяет обязанности выехать, если выдворение прямо назначено, но может стать аргументом при обжаловании. 
Про совет полицейских
То, что полицейские посоветовали «сделать регистрацию», — это нормальная практика. Они не выносят решений о выдворении, их задача — зафиксировать нарушение и назначить штраф (или передать дело в суд, если требуется выдворение).
Что делать дальше?
Если в постановлении есть выдворение, но есть и веские причины остаться (семья, работа), имеет смысл проконсультироваться с миграционным юристом. Специалист поможет собрать доказательства и грамотно обжаловать решение, если есть основания. 
Так что начните с копии постановления — это сразу прояснит ситуацию. 

Если у вашего мужа, гражданина Армении, остаётся законное основание находиться в России — например, заключён трудовой договор (граждане стран ЕАЭС могут работать без патента, а срок пребывания продлевается на время действия договора), имеется разрешение на временное проживание, вид на жительство или он проходит обучение, — то просроченная регистрация является лишь административным правонарушением, за которое он уже уплатил штраф. Сам по себе этот штраф не обязывает его покидать страну и не аннулирует право находиться здесь. В таком случае совет полицейских абсолютно верен: необходимо просто как можно быстрее встать на миграционный учёт по новому месту пребывания, подав документы через принимающую сторону, и никакого выезда не требуется. Если же законного основания для продления пребывания у мужа нет и 90-дневный безвизовый лимит, установленный для граждан Армении в течение полугода, уже истёк, то он действительно находится в России незаконно. Уплата административного штрафа без выдворения не легализует его статус и не восстанавливает право на дальнейшее нахождение в стране. В такой ситуации, даже если суд или миграционный орган не назначили принудительное выдворение, гражданин всё равно обязан покинуть территорию РФ, так как правовых оснований оставаться у него больше нет. Конкретный срок для добровольного выезда напрямую законом не установлен, однако каждая лишняя неделя просрочки увеличивает будущий срок запрета на въезд: при превышении до 180 дней обычно накладывается запрет на 3 года, до 270 дней — на 5 лет, свыше 270 дней — на 10 лет. Поэтому, если легализоваться прямо сейчас невозможно, самый безопасный вариант — выехать как можно скорее и затем вернуться уже на законных основаниях, например, заранее найдя работодателя, чтобы после пересечения границы сразу заключить трудовой договор и встать на учёт в течение 30 дней. Учтите, что простая постановка на учёт при уже имеющемся превышении срока не сработает, если в базе МВД зафиксировано нарушение режима пребывания. Однако существует возможность легализоваться без выезда: если муж в период нахождения в России заключит трудовой договор, то срок его пребывания будет считаться продлённым со дня заключения договора. Для этого необходимо, чтобы работодатель в трёхдневный срок уведомил МВД о заключении договора, а принимающая сторона поставила его на миграционный учёт. Таким образом, решение зависит от наличия или возможности оперативного оформления законного основания: если такое основание есть или появится в ближайшие дни — нужно срочно заключать договор и регистрироваться, и тогда покидать страну не придётся. Если же оснований нет и не предвидится, то мужу следует выехать из России незамедлительно, чтобы избежать накопления срока нелегального пребывания и серьёзного запрета на въезд. При выезде пограничная служба может зафиксировать превышение, поэтому перед отъездом стоит проверить наличие уже существующего запрета через официальный сервис МВД. Оплаченный штраф без выдворения — это хорошо, но он не даёт права на бессрочное пребывание, и повторное нарушение может привести к принудительному выдворению с помещением в спецприёмник, поэтому затягивать с принятием решения нельзя ни в коем случае.