Two things. A GAM is a non-linear model and is quite flexible. The degree of non-linearity is achieved by tuning the spline parameter degrees of freedom as well as introducing tensor splines to get non-linear interactions.
Second, the no free lunch theorms really make papers like the above a lot less telling than you might think. All I really get from them is that RF is a good modeling framework to try but for individual problems maybe try boosting on an SVM or a NN model.
