Payroll may be difficult to move to the cloud. Like HR it is very personal data. Reporting is potentially a big winner. Taxes too. Very interesting project. Good luck!
Tons of people already outsource your payroll which is already in the cloud.
Where I am most companies (from my experience) log on to their bank or other service provider using custom software.