Паспорт новый есть, но в инструкции сказано, что изменения вносить на основе свидетельства. А ей в ЗАГСе только штамп в паспорте поставили, а свидетельство о расторжении брака не далиДокумент Про порядок реєстрації актів громадянського стану в Україні . втратив чинність

А ми одну й ту ж Інструкцію читаємо?
2.13. Зміна записів у трудових книжках про прізвище, ім'я, по
батькові і дату народження виконується власником або уповноваженим
ним органом за останнім місцем роботи на підставі документів
(паспорта, свідоцтва про народження, про шлюб, про розірвання
шлюбу, про зміну прізвища, ім'я та по батькові тощо) і з
посиланням на номер і дату цих документів.

Точно. Вот действующие:

Правила державної реєстрації актів цивільного стану в Україні
Порядок ведення Державного реєстру актів цивільного стану громадян

Да. Я виду здесь, что нужен новый паспорт плюс свидетельство. Или достаточно паспорта? В принципе, если будет только паспорт, за это же штрафа нет

Паспорта достаточно.
Она могла сменить фамилию и без свидетельства о разводе - а просто написать заявление о смене фамилии только потому, что фамилия не нравится.
А вы не забудьте издать приказ:

Извините, информация была неполной. Небольшой нюанс. Это новый сотрудник. Смущало именно это. Но в трудовой уже была эта фамилия, так что, думаю,все будет хорошо. Сделала изменения на основании только паспорта.

По-хорошему, эти изменения работнице должны были сделать на предыдущем месте работы.

А вот это уже не нюанс, это фактор, существенно меняющий все дело - вы принимаете работника, у которого паспорт на одну фамилию, а трудовая - на другую фамилию.... Откуда у вас такая уверенность, что эта трудовая ранее принадлежала ей? Фамилия совпала?
Эти изменения ей должны были вносить на предыдущем месте работы, и я не понимаю, почему они этого не сделали.А с какой стати вы делали такие изменения?!
В паспорте, в отличие от свидетельства об браке, нигде не указывается, какая фамилия у нее была раньше! Вы, условно говоря, приняли Иванову с трудовой на имя Петровой, а потом неизвестно на каких основаниях стали вносить исправления?

М-м-м-м...но Вы же писали выше ответ на вопрос:
:reverie:

Я считаю, что паспорта не достаточно. Нужен еще документ, в котором виден переход с одной фамилии на другую.

Она развелась, когда не работала, трудовая была на руках. У меня есть копия решения суда, где сказано, какую фамилию меняет. Только в инструкции этот документ основанием не является. Поэтому неизвестно, могу я его вписать как основание в ТК или паспорта достаточно