I was able to replicate the effect. I tried the object with the basic UVs and cleaned up UVs. It's pretty much the same.
My conclusion is that it's highly scale dependent and sampling doesn't do much, even at max values.
The sampling areas are not properly "connected"/smoothed into each other. I, as a non-programmer, see this as an interpolation problem.
Color spreading can make it a lot better but it can go off rails into unwanted areas and at some more distant AO'd areas, the artifacts still appear.
Spreading is not the same as smoothing, so there might be an option that is missing. Sampling is afaik just affecting the accuracy.
There sure are a lot of workarounds for that, though baking AO gave me the best results, even with the standard c4d baker.(btw you can convert the AO bake into a vertex map and it might be more flexible than a bitmap.)
A curvature shader should be best for that task.(hope we get one)