Hey look - PayPal Announces ''PayPal Web Services''. Didn't see a mention of REST - but I'll sign up and find out more.

update - It doesn't look like there is any REST oriented direct HTTP access, only SOAP messages defined via WSDL.