Если буквально исполнять законодательство, то подавать уведомление вы не должны, так как уведомление подаётся только при заключении и расторжении (прекращении) трудового договора. В вашем случае срок действия нового патента перекрывает старый и оснований для расторжения ТД не возникает.
Однако смысл в подаче уведомления всё же есть. Иначе как при получении уведомления от работодателя - в ФМС поступает информация о том, что по данному патенту возникли трудовые отношения. В противном случае по истечении двух месяцев патент может быть аннулирован.
Поэтому следует поступать так. В любом случае к старому трудовому договору необходимо заключить дополнительное соглашение с реквизитами нового патента и ДМС. Дату этого доп. соглашения указываем в уведомлении и направляем в ФМС.
Только вышеприведённые действия были применимы к марту месяцу, в котором произошли описываемые вами события. В вашем случае подавать уведомление уже поздно. Остаётся уповать на то, что в сложившемся бардаке ФМС будет не до патента вашего работника.