couple of ideas:
never assume new batteries are good. Try to bypass your battery. I use my truck battery and "jump/bypass" the mower battery (if you don't have a load tester). If the mower rolls over and starts...you have a bad battery or a low state of charge. solve that. recharge the mower battery with a charger and try again. If it starts and runs then that solves the low state of charge issue. it if continues to have problems starting then your battery is either bad or the charging circuit to it is bad measure voltage from charging circuit during run...should read at least high 13 volts up to 15 volts, with mid 14 volts usually being typical.. Or it can be some kind of parasitic drain on the battery during storage.
next...for engine related diagnosis...quick things to do to rule out engine problems.
take both spark plugs out. rotate by hand...should rotate easily with very little resistance...if you take the valve covers off when you do this, you can see the valves moving....notice the auto compression release cycle...both valves should pop just slightly...if they don't, either that ACR has locked up and failed OR the valve lash and timing is bad. Do the valve lash clearance ...do it per the service manual. be precise. Does flywheel magnet match up to corresponding ignition coil modules at top dead center? refer to service manual for this position. Sometimes woodruff/keyway get slammed and timing is off. it's an easy thing to check. It's rare, but sometimes they keyway on the flywheel shaft gets slammed and drifts.. By checking the position of the magnet to the coils you can see if there is some misalignment that has affected timing. Try rocking the flywheel back and forth. There should be zero play.
has anyone adjusted valve clearance recently? it's a common mistake to bork this up when doing valve clearance and timing adjustments. I've done it twice and though I consider myself pretty good at it. Pay attention to magnet to coil position AND when top dead center actually happens.....and noticing when auto compression release occurs in the cycle. to the untrained or careless eyeball, that subtle movement can be hard to notice. Be precise.