Improving heading measurements from low cost compass module
While 'major' improvements is subjective, you can certainly improve your system more than it is (at least as you have described). Based on your problem description, it sounds as if your measurements may be non linear (you will have to confirm this). If this is the case, then a linear filter, such as the Kalman Filter, won't work well at all. 

From here, you need to determine if these 'large periodic deviations and noise' are normally distributed or not. If they are, then you can try a non-linear filter such as the Unscented Kalman Filter (If the deviations are truly 'large', the unscented filter is preferable to the extended as it is more robust to higher levels of non-linearity). If your noise and 'periodic deviations' are not normally distributed, then you will have to consider non-parametric approaches such as the Particle Filter.

As far as sensor calibration, you could try more advanced techniques, but typically the sensor manufacturer will supply some form of calibration procedure. This procedure is typically recommended unless you are absolutely sure about a different strategy.