Export your contacts and reimport them with the corresponding company relation.

Step 1: Import the contacts of type "Company":

Step 2: Edit your contact file and remove all contacts of type "Company", rename the field containing the related company name of the contacts to "parent_id"

Step 3: Import the edited file:

For reasons of data integrity, I would not check "Create if doesn't exist", but rather correct the import file, if it contains invalid data. But it's up to you, if you check it, you can save Step 1 and import all contacts at once, but you may have incorrect companies saved then (for example when your import file contains typos).

This is the result after successful import:

Enjoy!