That being sad, It's definitely better If you have a higher amount and you withdraw it once for all instead of doing it by really small amounts. Paper wallets are mostly for the long term storage so If you are planning to hold your bitcoins, I see no reason for buying a hardware wallet. You clearly can't spend funds from it directly but you will need to import the private key from the paper to another wallet and spend from there. In other words, If you are planning to spend from time to time then go with Ledger Nano S (I consider it as the best hardware wallets) otherwise Paper wallets are the way to go.
Sad fact is that sometimes we need small transactions and we do it often because for example you decided to play dice, than to pay for something or for someone and etc.
For minimizing fees it's better to use website which offers you low transaction fees (they cover some part) or no transaction fees (they cover everything). Last one you can't find but many websites (my local exchangers) offer 80% cover of fees).
Btw you can't find huge difference on fees on any wallet.