Wallets tend to have two main features: A) generate random private keys and B) given some private key, sign a transaction and broadcast this message to the network.
Pen, paper, and some dice (and a bit of work) can generate a private key for step A, which you can input into a hardware wallet, and which would have prevented the problem in the OP.
It’s also possible to write your own wallet software or use a “trusted” tool (eg: openssl or node) to create a private key, rather than rely on a random app or device off eBay to generate it for you.
The B) part is harder to do with pen and paper or an off-the-shelf tool as it involves a fair bit of protocol specific math—but it’s also harder to target in a hardware wallet supply chain attack.