Good question! It’s not something I consciously think about often, but into and onto are very tricky words: I remember one fellow from Mexico, who had grown up using en for both and finally thought he had it: onto means on top of, into means inside. Then he’s at the airport, and the loudspeaker announces that everyone should get onto the airplane. (I suspect what’s going on there is that we get onto ships, trains and passenger jets because those have large decks that we walk on, and into automobiles, small boats and the cockpits of small airplanes because those have compartments we sit in, but I don’t really know why my ancestors decided it should be that way.)
Personally (I’m American, and it might be different elsewhere), something going on or onto the pillow would make me think that the pillow is supporting it or holding it up, and something going into the pillow would make me think that the pillow is enclosing or absorbing it.
So, I would “rest my head on the pillow” or “elevate my injured leg on pillows.” I would also sit on a pillow or place an object, perhaps a piece of chocolate or a rose, on or onto a pillow. I would put a pillowcase either on, onto, around or over a pillow, and pull a sheet onto or over it.
In this context, he sank into his pillow because “sank” means that the pillow is too soft to support his head, so the soft pillow now surrounds his head. His head is, in a sense, partly inside the pillow. He might also carry something either in a pillow (if he wraps the pillow around it) or on a pillow (if it is on top of a pillow that supports it). He might cry into his pillow, because the pillow absorbs his tears, or scream into a pillow that muffles the sound.