Unfortunately there is no quick-and-easy fix for this. It's a result of a poorly designed home layout.
If you simply remove the inset for the stairs you will, as you note, remove the clearance for the stairs going down and you will likely create a situation where your stairway no longer meets code.
The right way here would be to relocate the stairs so that they no longer intrude on the kitchen cabinet space or to relocate the kitchen wall so that the stairwell intrusion is removed.
The simplest solution would be to do what the earlier cabinet installer did, cut away the backside of the cabinet to fit over the stairway and just live with the reduced capacity.
As I said, no easy solutions. Either live with it or fix it. The choice is up to you.