You'll want to setup a swing arm in the spindle to run an indicator at the corners of the table and then, as you guessed, loosen the bolts for the column and slide shim stock under the mating surface of the column to base attachment point and keep retorquing and adding shims until you get the right amount. I used .015 hardened steel shim stock and made U shaped pieces doubled over on themselves to keep adding until I had acceptable results. Make sure you have the bolts torqued tight before you do the first measurements - I found there is enough vibration that the bolts work free. I choose to run mine without thread locker and tightening the bolts is on my routine maintenance list.
It's not all that hard, just time consuming and the more meticulous you are the better your results will be. My first indication, since I didn't measure it when I first disassembled, cleaned and reassembled the mill, was uneven flycutting - I had kind of scalloped paths when flycutting since it was cutting only on one "edge" of the flycutter and now it cuts fairly evenly between the leading and trailing sides, sufficient for my needs. I could get it better but I still have a number of modifications I want to make so I haven't been too aggressive.
Good luck - you shouldn't have any problem.