No, sprites are not limited to four colors. All NPCs have two colors, one of them being a white. [Excluding black.] The only time this rule is broken is when the NPC is holding something of importance [i.e. a worker with a shovel, elder of the Zoras with his cane] or is a larger the normal sprite [i.e. a boss, King Zora.] That being said, there are only a handful of bosses that even break the two color rule, and it's generally because they are holding something.
Your updated sprite still has five colors. Two browns, two greens and an orange for the eyes. I feel like you aren't grasping GB style quite yet. The perspective of the sprite is off. His head should be at least two pixels lower, which would also begin to solve your height problem. You can argue all you want about GB style being small, but you said yourself in your first post that Deku Link needs to be shorter than regular Link, and as of right now, it's two pixels TALLER than him.
Start off editing NPCs before you create your own so you can begin to get a feel for how things should be colored and proper ways to make shadows with only black, white and a color. GB is a very simplistic style, but is hard to recreate because of all the restrictions. If I were you, I would edit on of the sprites of the children playing ball to find the proper height for Deku Link.