Does anyone know of a company/startup which provides "remote employment as a service", including managing payroll, days off/holidays, local law/tax compliance and the whole slew of paperwork?
Another solution I have seen in real life is to ask the foreign "employee" to create a one-person company that bills the "employer".
The process then is simply making a periodic invoice from my company to yours; the ongoing costs involved would be whatever an international money tranfer costs for you, + I'd pay something like $50/mth to a local accounting company to handle all the taxes&reporting for that.
I don't know of any full "remote employment as a service", but there are a lot of outsourced accounting companies who'd do the taxes & paperwork - most local small businesses do it this way, since there's not enough work to have a full-time accountant/finance person on board. Actually executing payments and managing days off is a bit trickier, since the first requires full access to the company funds, and the second involves managing people, which is hard to outsource - you probably could get them to calculate 'what is owed to whom' by the local laws, but you'd have to pay salaries yourself & schedule vacations directly with the employees.
Also, at least in Germany, if you only have one client/customer, you're vulnerable to committing a tax/social security offence called "Scheinselbstständigkeit" (roughly: faked entrepneurship), as you'll end up paying less in taxes, social security and insurance than a full-blown employee and people have abused this in the past to maximize their profits on cost of the employee or the systems.
As for that "Scheinselbstständigkeit", I believe most other countries have some similar legislation. It's not an issue with freelancers as you have rotating clients, even if it's only one at a time; but yes, if you're creating it just for a single employment then that can be treated as tax avoidance - having the employer run a shell-subsidiary-branch would be preferred in that case.
If you get, say, Facebook or IBM or Microsoft large then you just have lots of regional offices to handle this.