I got the same error message and noticed that when it happens my bluetooth mouse disconnects. So the problem revolves around the bluetooth connection. It's not just related to the S pen. Is it the bluetooth driver or a hardware problem?
I was able to solve the connection error and Air Action gestures issue by updating the bluetooth driver using the Samsung Update app. Now Samsung Settings shows the S Pen Air Actions are available with 100% battery. I verified that all of the Air Actions work. Good luck!
FYI, I had the same problem again this week. I reinstalled the bluetooth driver since that worked previously, and it is working properly once again. I'm not sure what caused the bluetooth driver to stop working twice within 3 weeks.