Is Zenefits still the best way to go? What about accounting? We need to see clearly where money goes. Freshbooks?
I say this as a tax lawyer, finance guy, and small business owner. I have lived (and continue to live) in this problem space.
HR. I am sorry, but software will not solve your problems. Governments (and you are dealing with more than one) tend to be actively hostile to employers. California (where I am) is the worst. You will make mistakes. A single overtime claim can cost you tend of thousands of dollars.
For HR I hired a consultant to document everything. The consultant's work was cross-checked by a labor lawyer. We do quarterly reviews of the employee manual and all procedures. You have to live by the rules you write.
I hate being an employer. I really like the people who work with me. They are great.
You, as a founder, should preserve your attention. You should also protect your reserve of courage -- don't have incipient, nagging fear that you are doing it wrong. I suspect you are there now, by your comment about converting your people from contractor to employee.
Accounting. Hire a really, really good bookkeeper. At your size you need someone in house, at least part-time. We have have our outside accountant and two part-time bookkeepers (a junior day-to-day person and a senior manager-level person) feeding data to our accountant.
Software: Xero. My personal opinion is that QuickBooks is shit, but you use the tool that the craftsman favors. Our senior bookkeeper loves QuickBooks Online and can make it sing.
International. I happen to be an international tax lawyer. I know about the complexity of having employees in other countries. This simply means that the true cost of having a distributed team is higher than you think.