Но сейчас пришло постановление от пристава и запрет на выезд на девичью фамилию

Вера, вы абсолютно правы, что переживаете — ситуация действительно непростая, но вполне решаемая, особенно если действовать быстро и грамотно.

Давайте разберем по порядку:

Что произошло?
Вы сменили фамилию 8 лет назад, но пристав направил постановление о запрете на выезд на старую (девичью) фамилию. Это уже нарушение, так как после смены фамилии пристав обязан исполнять действия в отношении вас как нового юридического субъекта — с актуальными паспортными данными.
То, что по вашей текущей фамилии в базе ФССП — «чисто», уже говорит в вашу пользу. Но если запрет формально есть — могут не выпустить, особенно если сведения о старой фамилии все еще связаны с вашим паспортом в базах пограничного контроля (ФТС).
 
Что важно понимать
Пристав не снял запрет, несмотря на оплату долга?
По закону, пристав обязан в течение 3 рабочих дней после поступления оплаты вынести постановление об окончании исполнительного производства (ч. 1.1 ст. 47 ФЗ №229-ФЗ «Об исполнительном производстве») и в течение 1 дня с момента вынесения — направить постановление в погранслужбу ФСБ для снятия запрета (ст. 67 ФЗ №229-ФЗ «Об исполнительном производстве»).
Если дело «сфабриковано», это будет предмет отдельного разбирательства — но для того, чтобы сейчас улететь, главное — оперативно добиться снятия ограничения на выезд.

Что делать прямо сейчас — пошагово
Шаг 1. Немедленно связаться с приставом
Позвоните или, еще лучше, лично идите в отдел ФССП, выносивший постановление, и требуйте:

Показать основание для запрета (кто взыскатель, что за долг, как уведомляли).
Объяснить, почему производство идет по недействующей фамилии.
Вручить платежное подтверждение и заявление о снятии ограничений на выезд, с требованием в тот же день вынести постановление об окончании ИП и направить информацию в Погранслужбу ФСБ.
Пример формулировки в заявлении:

Прошу в соответствии с ч. 1.1 ст. 47, 67 ФЗ №229-ФЗ «Об исполнительном производстве»:

признать исполнительное производство оконченным в связи с фактическим исполнением;
немедленно снять ограничения на выезд за пределы РФ;
уведомить меня письменно о снятии запрета и отправке сведений в Пограничную службу ФСБ.

Шаг 2. Лично отнести заявление и потребовать копию постановления
Не ждите «по почте» — настаивайте на немедленном решении, особенно если пристав находится в вашем городе. Не уйдите, пока:

не получите копию постановления об окончании ИП,
не увидите, что они отправили сведения в ФСБ через СМЭВ (электронный канал связи).

Шаг 3. На крайний случай — добивайтесь срочного снятия запрета через суд
Если пристав отказывается, или нет времени — можно подать заявление в суд о признании запрета незаконным и одновременно — ходатайство об обеспечительной мере: приостановить действие запрета.

Это — крайняя мера, но суды по таким делам иногда рассматривают в ускоренном порядке, особенно если предоставите:

билеты на рейс,
визы,
подтверждение оплаты долга,
паспорт с новой фамилией,
выписку из базы ФССП (где «чисто»).

А выпустят ли вас сейчас?
Это зависит от того, как быстро пристав отправит данные в ФСБ. Даже после оплаты, запрет может висеть в базе пограничников до 2 недель, если пристав тянет. Это — частая проблема.

Важно: даже если долг оплачен, при наличии записи о запрете на любую фамилию, связанную с вами, Пограничная служба может не выпустить, если запись еще не снята. Особенно если в их базе две фамилии (до и после смены) связаны.
После вылета — обязательно:
Подайте жалобу на действия (бездействие) пристава в прокуратуру и в УФССП.
Требуйте признать производство незаконным, если «сфабриковано».
Пишите заявление на взыскание морального вреда и убытков, если вам пришлось сдавать билет, отменять поездку и т.д. (ст. 1069 ГК РФ — вред, причиненный органами власти).
Что взять с собой в аэропорт:
Паспорт с новой фамилией.
Копию заявления приставу.
Подтверждение об оплате долга.
Справку/выписку из ФССП по своей фамилии (где «ничего нет»).
По возможности — копию постановления об окончании ИП или хотя бы номер ИП, ФИО пристава, контактный телефон.
Если ответ был для вас полезным, отблагодарить юриста можете по этой ссылке. Был рад вам помочь) pravoved.ru/pay/lawyer-reward/id/4147135/