Ergänzend zu den bisherigen Hinweisen würde ich zunächst in der Kontakte-App nach einem der betroffenen Namen suchen.
Ist der Kontakt dort ebenfalls nicht mehr vorhanden, prüfe unter „Einstellungen → Apps → Kontakte → Kontakte-Accounts“, ob der bisher verwendete iCloud-, Google- oder Exchange-Account noch aktiviert ist und die Synchronisierung von Kontakten erlaubt. In diesem Fall würde ich die Favoriten vorerst nicht neu anlegen, da die Einträge nach Wiederherstellung der Kontaktsynchronisierung möglicherweise wieder korrekt zugeordnet werden.
Sind die Kontakte dagegen vollständig vorhanden und nur die Favoriteneinträge betroffen, ist der von MRGL beschriebene Weg zum erneuten Hinzufügen passend.
Liebe Grüße! 🌺