if(Math.abs((currRotation + 180 - destinationRotation) % 360 - 180) < speed)
I don't know much Java, but I suspect that code will do the wrong thing when `currRotation' is 0 and `destinationRotation' is 359. The angles will be considered to be 359 degrees away, instead of 1.
I really think you should give up using angles: They force you to use expensive trigonometric functions all over the place, they make the code hard to get right because there are so many special cases that one has to consider, and in the end it is hard to decide if that code won't blow up in some circumstances.
The code using complex numbers is really much much simpler, once you get past the mental block of representing rotations as complex numbers with mudulus 1. I don't quite know why you dismissed the idea earlier.