I want to reject certain sender-recipient combinations, with a specific message for each such combination.

Set up a file (or database) containing the messages, keyed by the combination, for example:

sender1@sdomain1=>recipient1@rdomain1: blocked because...
sender2@sdomain2=>recipient2@rdomain2: blocked because...

If you have lots of recipients for the same sender, it might be easier to generate this file from more convenient data. In your ACL that is run for each RCPT command, you can then put:

deny message   = ${lookup{$sender_address=>$local_part@$domain}\
                 lsearch{/that/file}}
     condition = ${lookup{$sender_address=>$local_part@$domain}\
                 lsearch{/that/file}}{yes}{no}}

The condition is tested first. If the lookup succeeds, the condition succeeds so access is denied. The message is then expanded, but the lookup won't be repeated, because Exim will have cached the previous result. This approach blocks only incoming SMTP messages. If you need to do similar blocks for messages that do not arrive over SMTP, you have to set up a suitable redirect router with a :fail: setting.