Steel Beam in Basement
As much as I dont like to push the services of Home depot, they do have the material you are looking for.
They have a Quikrete non shrink grout for about $12.00 a 60 lb bag and also a rapid set non shrink grout for $19.00 for a 50lb bag. The rapid set is a great product, I use it to do structural patching in small areas, but sets up in about 10 minutes which will make the hand work necessary for infilling base plates hard to keep up with.
As far as how to do the work, Bob is right you need to fill in all the voids. Normally this is accomplished with a sawing motion from a strap like steel strapping or a thin piece of steel or the like. The type of material for the piece is not important it just needs to be thin so you can densify and remove all the voids from under the plate. Also it is normally best to keep the material hand workable and not flowable so you can PACK it in the area.