Heh, I beg your indulgence for my cheeky comment, I of course know nothing of this matter, it seems easy, as all those task you mentioned can be converted to single rules. Not a weekend worth of work, but perhaps 20 weeks worth of work for a prototype?
Single rules, yes. For each State in the US. And every other country in the world. And that can change at any time of the year. Oh, and nobody form those various state and federal government agencies are reaching out to tell you when and what is cahnging.
And GP just listed a few things off the top of his head - there are literally hundreds of complexities in doing this that he glossed over...
Dude. Stop while you are ahead. Payroll is edge case upon edge case upon edge case. And if you fuck up any of those edge cases, you are fucking up some poor soul's livelihood (or maybe making their day and the expense of their employer!).
Sure, you can create a non-union, full-time, no overtime, citizen/permanent resident, no taxable benefits, CA resident and company location only payroll company “trivially,” but who the hell would use your software when there are ones that handle much more complex situations?