CR 15 works for me!
Take iron golem construction, boost the cost a bit, and swap cloudkill for overland flight and maybe heat metal?
How's this?
A furnace golem’s body is sculpted from 5,000 pounds of pure iron, smelted with rare tinctures and admixtures costing at least 15,000 gp. Assembling the body requires a DC 20 Craft (armorsmithing) check or a DC 20 Craft (weaponsmithing) check.
CL 16th; Craft Construct, geas/quest, heat metal, limited wish, overland flight, caster must be at least 16th level; Price 175,000 gp; Cost 95,000 gp + 6,400 XP.
Rock damage looks good.
No need to increase CL, as the other CR 15 golems (drakestone, sickstone, and Sardorian) are all CL 16th.
Updated.
Finished?