How to automatically delete all product displays when a product is deleted?

1) You need the commerce product id (which is the one of the commerce product that has been deleted) and not the nid because of the reference you are using. If this parameter is not available you must bring it into scope using a proper validation.

Notice that after deleting the commerce product there is no product id so no products are referencing it. The correct trigger should be "before deleting commerce product" but does not exist by default.

Also, how do you handle a Product display (node) with multiple product variations? Should this node be deleted? There should be an additional condition to check if there are other variations for the same product display. Except if you have a 1 to 1 reference.

2) Another option should be to do the opposite which is to fetch all the nodes (Product displays) that have an empty commerce product reference. This is easier to create.