The difference between using your card and using PayPal is slight. Many web sites say they accept credit cards but the payment is processed through PayPal.
I would agree that PayPal can be a hassle if the other party has not used them before (like my NOCHEX experience). I would, however, expect a lot of businesses to accept credit or debit cards. Otherwise, myself, I would certainly ask them to consider accepting PayPal. Any good business should always be willing to listen to the customer.
PayPal may not be as suitable as your original post suggested. I guessed that you were wanting to send regular payments to the same people (like a relative studying or working abroad, perhaps), but it is still worth not dismissing the service.
________.