If I understand this correctly, you have one instance A where some stored procedure inserts and deletes rows in a database on instance B by means of direct INSERT and DELETE statements with four-part notation. Now you are looking to how to solve the permissions on server B.

Seen from the perspective of server B, this scenario is no different from the users connecting directly from SSMS to run INSERT and DELETE statements. (Unless you set up a login-mapping on server A, but this has other issues.)

It is difficult to answer the questions what you should do with the instance logins, because I don't understand what the problem might be. But then again, I don't know your site. However, the paragraph above may give a clue: this is the same as direct access from SSMS or whatever.

You should of course not grant access directly to users, but to an SQL Server Role or a Windows group, but you seem to have grasped that already.

The GRANT statements would be those you listed, and you are right in granting minimal amount of permissions.

For the question about stored procedures, I am again puzzled why you ask. Is something more hiding here?