Will try the electrum verification route first as it was a real hassle doing the offline transaction safely last time so rather not have to do that again but may need to if the tx fees are too low like you say.
Although more time consuming, it is the safest way to make your transaction. As soon as you import your private key to a computer with an internet connection, there is always a risk of compromise. I would at least import your transaction first to see what fee it is paying and whether or not you would be happy with that fee. If not, then I would opt to either import your wallet to an airgapped computer or use CPFP as I mentioned above, just to be sure of the safety of your coins.
Correction: paper wallets are almost always only made with private keys, using a seed phrase when you create a paper wallet is especially uncommon so it doesn't even need to be mentioned.
I would disagree with that statement. I have a number of what I would call "paper wallets" (i.e. they exist on paper only and nowhere else), and all of them are comprised of written down seed phrases as opposed to printed out private keys. I don't see any disadvantage of using a seed phrase compared to private key in this instance, whereas there are numerous advantages such as being able to hand write instead of using a printer with a far lower chance of making an error, not having to sweep the entire wallet each time you want to spend from it, no concerns regarding change addresses, being able to deposit coins to an already created wallet without having to reuse addresses, etc.