Many years ago I looked into gifting 1BTC to each of my God sons, who had just been born. That gift would be worth a fair bit today, but I didn't do it because I couldn't figure it out.
How could I do this today? Remember, the recipient is 0 years old and can't upload their passport :)
Generally, I like the idea of giving away bitcoin as a gift.
So here's one approach for those who are still willing to give away cryptocurrency as a paper wallet, in spite of the disadvantages that Murch correctly mentions.
Here's what I did in similar situations (birthday presents to adults):
The upside of this approach is that people are used to treating physical money (bills) as an asset - they keep it in a safe place and usually don't misplace it or accidentally throw it away.
The instructions on how to use a Bitcoin private key are on the internet - for a user with the understanding of the significance of the keys and some technical skills it's not that difficult to install an Electrum client and import a private key. For the less skilled or those in doubt, they have received the promise of my assistance along with the present.
The decision if you want to keep a backup of the private key is up to the level of trust between you and the gift recipient: Under normal circumstances, I would delete my copy of the private key: When ownership changes, the new owner should be the sole owner of the keys.
Gifting Bitcoin to novice users is difficult. First, your gift is tied to an obligation. In order to make use of it, they need to invest time to understand it and how to access it. This causes such gifts often to not properly connect. Secondly, the Bitcoin gift is often forgotten about because the recipient doesn't have an immediate use for it. Often Bitcoin gifts are somewhat impersonal (e.g. a paperwallet similar to a gift voucher), so they tend to get displaced. Optimally, the gift is personal and unique enough to be kept track of as well as hardy enough to survive until the recipients interest is piqued.
This brings us to another issue. The instructions how to use the Bitcoin gift must be sufficiently accessible and longlasting that a novice users can follow them now or in two decades. And they must be stored with the gift! On the other hand, it should be safe against being stolen through casual observation, like e.g. cleaning helpers. Even using some service is hit-and-miss: the space is only 11 years old, nobody knows which services will still be around in 12–16 years when your god sons get interested?
I surmise that you might have the best chances of success by investing significant effort to make your gift very personal (ensuring that it is treasured) and find a way to integrate instructions with the gift so they don't get separated.
You will want to keep a backup in case it does get lost.
