Recently, when I tried creating a lookup relationship with the Product (Standard Object) from the custom object, I got the below error though I was not trying to create the Master Detail relationship:
You cannot create a new Master-Detail relationship on an existing custom object if records already exist. You must first create a Lookup relationship, populate the lookup field with data in all records, and then change the relationship type to Master-Detail.
Moreover, the custom object was a new object and it did not have any records. I was bit confused and the error message is misleading as well. Then, after googling, it looks like you can create a lookup field to Product only if you allow to clear the field if the Product record is deleted(please check the below screenshot for your reference):
Please let me know for any clarification.