Normal force doesn't do work . You are thinking right that your Center of Mass has got a displacement and it's the displacement of the center of mass which counts in the equation.
What your are not seeing is that The Normal Force doesn't last during the interval of displacement . Infact Displacement begins after Normal Force has gone down to 0.
For eg: You hit a pencil . During the time of your hit the pencil displaces only a very small amount. And that displacement causes the work done by you. After that ( without friction ) the pencil moves with a constant velocity.
Here the Normal Force doesn't even cause the displacement . Its your muscles.
Consider a block on an inclined plane . You apply force horizontally to the plane . The normal force being perpendicular to the displacement doesn't do any work. But its the vertical component of normal force the cause the block to rise. Effectively the Normal Force has caused your applied force to raise the block ( your applied force doesn't raise it directly ).
Similarly the normal force here causes you muscles ti do the work .