Yeah I see how it could possibly work.
The relay takes a toll from the user in sats, then adds a random nonce to the event until an event ID with N leading zeros is found, just like in Bitcoin. This event ID would tell other relays that the required PoW had been performed on the event.
It would have to be up to the relay operators to ensure they were charging enough to pay for their own computing costs.