Как поступить работодателю?

декретнице, чтобы в очередной отпуск пойти, надо, как минимум, прервать отпуск по уходу за ребенком. а временный сотрудник у вас принят, я так понимаю, на период отпуска по уходу за ребенком основного работника. у основного закончился отпуск по уходу а у временного тут же закончился трудовой договор. т. е. вы его вполне законно увольняете и выплачиваете компенсацию за неиспользованный отпуск.
имейте в виду, что отпуск декретнице положен, если остался неиспользованный за прошлые периоды. время нахождения в отпуске по уходу за ребенком в стаж, дающий право на отпуск не включается, а предоставлять отпуск "авансом" за рабочий год который еще не начался работодатель не обязан.
отказать декретнице, если у неё есть право на отпуск, работодатель ни как не может. и в том, что вы до отпуска по БиР не предоставили очердной отпуск тоже ни какого "косяка" нет. отпуск "декретнице" предоставляется по её желанию, а ни как не по желанию работодателя.

Работодатель вправе отказать сотруднику в сроке отпуска.
Одному или обоим сразу. Я бы отказал декретнице. Насиделась, хватит.
Это раз.
Во вторых - почему вообще у вас временный по отпускам ходит? Временным не положено.
Это два.

Уволить обоих и не оплачивать вообще ничего

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

Ну а если бы "декретница" не вышла пока. Тот другой работник все равно же в отпуск бы пошел. То есть на это время всеравно так или иначе Вы без сотрудника. А дальше оформляйте временному отпуск с последующим увольнением, а "декретницу" отпускайте в отпуск и ждите.