So if you have 1 BTC on a paper wallet and spend only 0.25 BTC, the change (0.75 BTC) goes to a newly generated, unused address.
[...]
With that being said, if private keys allow access to only one address but when you make a transaction the change goes into another one... where will the change go? Into an address you do not have ownership over.
No, not necessarily.
This completely depends on the wallet used.
If using electrum for example, transactions using the imported private key will send the change back to the original address.
Paper wallets have private keys written on them, not seeds.
Not necessarily.
It depends on the wallet OP has. But usually this is the case, yes.
What is the safest way to do it?
I heard is not safe to make more than one transaction with coins swiped out from cold storage.
So would you advise me to send just a few satoshi to my hardware wallet to test or can I send ALL of them, after triple check of the address?
The safest way would probably be to use a desktop wallet (e.g. electrum) together with an offline computer.
Download the original electrum and verify its signature. Then use an offline device (or a live booted linux distro in offline mode) with electrum to create and sign a transaction sending the funds to your hardware wallet.
Then copy the transaction to a USB stick and move it to an online PC to broadcast it.
This can either be done with all of your funds or with just a few satoshi first to check that everything works as expected.
If you do everything correctly (this means, to check the change address), then it is fine to send multiple times from the same address / paper wallet.