Regardless of where the transaction occurs, the "rewards" (be they cashback, points, miles, etc) are paid by the financial institution that issues the card (lets call then "banks" for simplicity). As you've implied, these would normally at least in part be funded by the "interchange" fees that the merchant is charged when you make a credit card transaction.
Even without considering EU regulations, there are many occasions where the value of the rewards is higher than the fee that the bank charges for the transaction, and in these cases the bank will be losing money on that specific transaction. This is especially true for credit cards that offer variable rates of points/cashback based on the merchant types (eg, 5% at gas stations, 2% for travel, 1% elsewhere). In these cases the banks intent is generally to get the card holder to use their card everywhere, so even whilst they may lose money on the gas station transactions, they make it up on the 'elsewhere' transactions. They may also make money from things like the credit card annual fee, or from other requirements that they enforce on the customer (eg, some higher-rewards cards are only available to customers who have a certain amount of money invested with the bank).
Specifically for EU transactions on non-EU cards, there's going to be 2 main situations. Firstly, may cards charge an "international transaction fee" to the cardholder for all transactions outside of their home country, which can be as high as 3-5% of the value of the transaction. In these cases, this fee would obviously cover the cost of any additional bonuses they were offering to the card holder.
The second situation is for cards with no international fee. In this case the bank is simply doing the same thing they are doing for the 'gas station' case mentioned above - they are losing money on that specific transaction, with the expectation (maybe "hope" is a better word?) that they will cover that cost elsewhere - either from the annual fee, domestic transactions with higher interchange fees, etc. Generally (but certainly not always) cards with no international fees are ones that have higher annual fees, and often only available to those with higher credit scores which would generally imply someone that spends more on their credit card domestically (obviously this is an over-simplification, and there will be countless exceptions, but the general statement is correct).