[joshpadnick]

We[1] are a fully distributed team and also ran into this problem when we hired our first team member outside the US. There are lots of players[2][3] in the "Global PEO" market that have corporate entities in multiple countries and will handle payroll and benefits for you, but caveat emptor, these solutions are shockingly expensive. The average cost was 18% of the remote worker's salary (!), which I personally considered insane.

We ultimately went with a company[4] that had a different model where they connect you with a local PEO in each market and present a common UI on top of all the disparate local PEOs so that you get a company that specializes in just that country, but a common UX no matter how many countries you work with.

I liked the model, and more importantly, it was a fixed fee and much less expensive, and they published pricing. Disclosure: We made the decision to go with them, but haven't started working with them yet.

[1] https://gruntwork.io

[2] https://www.globalization-partners.com

[3] http://globalpeoservices.com

[4] https://papayaglobal.com