Why do people pay for hardware wallets when you could just …

Make sure that paper wallet is generated offline and by a safe script that has been vetted by someone to make sure the randomization is correct.

This is why paper wallets is a bad idea today as most newbies will use a website to generate one.

If I can't trust the algorithm in a paper wallet generator why should I trust the software in a hardware wallet?

It is a good question. Everything comes down to trust in the end, we've got to put it somewhere or "be all knowing" (which is impractical).

I think a good way is to go for wallets or services that has been used by authoritative users in society.