Of course you need to know where deviation=0 is:
If this is just slightly wrong, your bot at best will drift away more or less fast.
If there's no way to detect this properly, you just can solve it by contolling both angle and location in an even more complex 2 level control loop, controlling the average output to be 0.
2deg -> noise, but motor won't start
This is another main problem, IMO: due to motor characteristics, control does not start linear at 0 but has a dead band.
2° is rather late already, but you'd need something that makes your bot act "immediately" (even a decent Integral term might sum up rather late). When on ground, motor needs more power to move, of course. If linear control ( pure PID with a good I in it ) does not help, experiment with a nonlinear term:
analogWrite(LPWM, output+M_BIAS);
...
analogWrite(RPWM, -output+M_BIAS);
Another idea ( I do not know Arduino's servo or stepper software, though ): What about instead of using normal ( high frequency ) PWM, do a similar PWM on a low frequency: switch the motor really ON (such that it turns) for a more or less long moment during your control cycle.
BTW:
I did not get how you measure positive and negative angles.
And I understand you have 2 outputs for forward and backward ( or left/right , depending on your point of view )
I do not fully understand how your code in the initial post around the line
output = -1 * output;
works, and why you need those 2*2 cases.