And why not do so for them specifically? If you still have protections apply to larger companies, then it becomes a matter of choice for employees to choose small or large. But if you apply to everybody, and it kills small businesses, you're strictly worse off - if you can't land a job at one of those larger places, you're outright unemployed.
And also there's a big ethical question here if you create an excemption for small business, because you create a two class workforce where parents in small companies lack what is arguably a very fundamental right.
So I guess it is a complicated issue, but on the specific matter on paternal leave I would argue that a universal protection at the cost of small business activity is preferable. Every parents should have the same rights when it comes to child care.
The way I see this, the fundamental right here is to have paid parental leave in general, not a right to have it at any particular workplace specifically. Thus, so long as those who need it can get a job that offers it, I don't see any pragmatic reason to require all businesses to do so. So long as it's clear in advance - so people who e.g. don't plan on having children can go seek employment with small businesses. It's not an insignificant part of the population, so why remove an option for them?
There is incentive to re-hire anyway if you have open positions as you get someone already familiar with the work. Forcing employers to do so is a problem for smaller companies having many non-duplicated positions though.
I respect people who want to run very small businesses, but we can't realistically make policy for them if we want to guarantee some basic welfare and labour protection.
Small businesses are often so unprofitable, have so little savings, and are so exposed to risk (as in this pregnancy case), that you realistically need to scrap so much protection just to accommodate them.
So the answer to the question of how to combine very small business and paternal leave is quite simple, you really can't. It's a policy that favours middle-sized and large businesses who generate more profit, suffer less from a few workers dropping out, and can organise these benefits.