It appears that the only way to deal with tool changes given the current version of Carbide Motion is to separate each tool into a separate g-code file. When I tried to run a single g-code file that included multiple tools, CM would stop and prompt for the tool but there is no way to move the router to a safe spot for that change or raise the router to allow a change. There is also no way to zero the new tool. From other posts and replies here it sounds like this was really designed for the Nomad that has a built in probe. Maybe we need that on the Shapeoko.
After setting the x/y/z zero, pick a spot on the bed and place your probe there and define that x/y position to CM. When you start the g-code file CM prompts for the first tool. When you click on Continue CM moves to that probe location then homes and probes the z-axis to get the absolute position when the tool engages the probe. CM then needs to remember that absolute z position. Then it goes along it's merry way until a tool change occurs. It then homes the z-axis, moves to the x/y position of the z probe (or maybe a safe location defined separately) and pauses for the tool change. When you click on Continue it moves down until it engages the z-probe. Now it takes the prior absolute height from the first probe and this new height, does the math and figures out where the tip of the tool is. Since the z probe for a tool change is totally separate from your work piece it doesn't matter if the corner you originally used to set the x/y/z zero may have been machined away. It's just determining the relative difference between two probes, one from the first (or prior) tool and this one to adjust that zero height accordingly. It would be important that the probe is not moved during the entire run so it has to be somewhere that won't be in the way. That may be difficult if you're working on something that covers the entire bed.