I think the first mention in the revised edition is from Sylvia Pittston:
“It’s him that will come as the Antichrist, a crimson king with bloody eyes, to lead men into the flaming bowels of perdition, to the bloody end of wickedness, as Star Wormword hangs blazing in the sky, as gall gnaws at the vitals of the children, as women’s wombs give forth monstrosities, as the works of men’s hands turn to blood—”
The first mention other than the revised was in W&G:
"At that moment the revving sound of an engine tore into the air. From beyond the fence, on the Forty-sixth Street side of the lot, chugs of dirty brown exhaust ascended like bad-news smoke signals. Suddenly the boards on that side burst open, and a huge red bulldozer lunged through. Even the blade was red, although the words slashed across its scoop—ALL HAIL THE CRIMSON KING—were written in a yellow as bright as panic. Sitting in the peak-seat, his rotting face leering at them from above the controls, was the man who had kidnapped Jake from the bridge over the River Send—their old pal Gasher. On the front of his cocked-back hardhat, the words LAMERK FOUNDRY stood out in black. Above them, a single staring eye had been painted."