You solve the issue by introducing more middle-shades and evening out your lightness spectrum on the shades you already have! The middle of the range is where you need to work most, not the extremes. Leave the top of the range for small highlights and the bottom of the range for dark shadows. Right now, whereas you've got the right amount of dark in your picture, when you need to bridge the gaps. You have 33 colors in your image, I am not sure how, I see about 11 handpicked in that little palette you have on the top-left. Also they're not really grey, they have small saturation and hue values.
Crash course on pixel art:
1.You'll never be in control of your palette until you can select every index and change its HSL values in real time in a real pixel art program. If you're using photoshop, you'll never control your palette like a person that uses graphics gale or pro motion or any other program where you can edit every index entry in real time on the fly. Even if there are workarounds, they'll never be as fast as a real pixel art program does it, and what is not fast, whatever you have to do extra labour to achieve, your artistic reflex will be to do less. And pixel art is control, you need to control more, not less.
2. Small palettes are manageable, this is why pixel artists use small palettes, not to look 'retro' (well, not all of them). Even the palette in my edit is too big, your image can be done with 16 colors or even 8 colors if someone wants to accentuate the planes and doesn't care about AA so much. If you don't know how many colors you've got in a picture at any given time, you won't be able to control the palette.
3. An optimized palette is one where you can convey a lot of different hues and gradations using interchangeable 'linking' colors on a small linear index. That stuff can only be done right in a deluxe paint-like program. You won't be able to map it out on the little right corner of the screen.
4. conveying small shapes that flow into each other well and avoid banding and mudded up volumes is what pixel art is all about. If you have very large flats and too many colors to convey them with, take away colors! Reach a balance between what you are drawing and how much you need to use to draw it.
Are you starting to see why pixel artists work like pixel artists and not like photoshop-in-small-resolution-artists? There is wisdom in taking the aesthetic form to its logical workflow conclusion. Pixel art isn't 'pure' because some guy on the internet made up some rules and marketed them, art made of pixels looked best when done in a certain methodology set and that's what informed people's opinion of what a pure version of the nascent medium would look like.
Here's an edit


And yes, try to avoid just doing a gradient that follows the shape of the mask from point a to point b. Instead think of the thing as if it's a low-poly flatshade 3d mesh at first. Just use straight lines and cut through the complexity of the real thing.