You cannot say All the staff wish you didn't leave so soon.
But you can say The staff wish you didn't have to leave so soon.
Also OK: *The boss wishes you wouldn't leave so early." or "The boss wishes you didn't leave so early".
In that final sentence, the difference between it and the OP's original example (All the staff wish you didn't leave so soon) lies in the difference between "so soon" and "so early".
That which is about to happen "soon" is a single occurrence in the future, whereas the boss is concerned with something that happens on a regular basis, your not staying in the office until later in the evening (American scenario).
I wish it didn't have to be this way, but you're fired. You never come into the office on weekends and you never stay later than 7PM. I let it be known that I wished you didn't leave the office so early. You ignored those hints. You'll never succeed here, Jones. All the staff may wish you weren't leaving so soon after being hired, but you set a bad example, and you have to go.