The shading on Shiva (as with every other character) is indeed vertex color. 3D Studio Max supports Vertex color, I can confirm that, but I'm not sure if any of the formats we can export the models as supports that sort of information. I was working on one that did, but never got to finish it.
If you're going to edit the models, it would probably be best scrapping the baked shading completly, though. I'd paint the model with plain colors and ask 3DStudio to give me an ambient occlusion lightmap.