Going to Gargantuan...
Stone Golem
Gargantuan Construct
Hit Dice: 40d10+60 (127 hp)
Initiative: -2
Speed: 20 ft. (4 squares)
Armor Class: 29 (–4 size, –2 Dex, +25 natural), touch 4, flat-footed 29
Base Attack/Grapple: +30/+60
Attack: Slam +43 melee (4d8+17)
Full Attack: 2 slams +43 melee (4d8+17)
Space/Reach: 20 ft./20 ft.
Special Attacks: Slow
Special Qualities: Construct traits, damage reduction 10/adamantine, darkvision 60 ft., immunity to magic, low-light vision
Saves: Fort +13, Ref +11, Will +13
Abilities: Str 45, Dex 7, Con —, Int —, Wis 11, Cha 1
Skills: -
Feats: -
Environment: Any
Organization: Solitary or gang (2–4)
Challenge Rating: 19
Treasure: None
Alignment: Always neutral
Advancement: 41–42 (Gargantuan)
Level Adjustment: -
Combat
Slow (Su): A stone golem can use a slow effect, as the spell, as a free action once every 2 rounds. The effect has a range of 10 feet and a duration of 7 rounds, requiring a DC 30 Will save to negate. The save DC is Constitution-based.
Immunity to Magic (Ex): A stone golem is immune to any spell or spell-like ability that allows spell resistance. In addition, certain spells and effects function differently against the creature, as noted below.
A transmute rock to mud spell slows a stone golem (as the slow spell) for 2d6 rounds, with no saving throw, while transmute mud to rock heals all of its lost hit points.
A stone to flesh spell does not actually change the golem’s structure but negates its damage reduction and immunity to magic for 1 full round.
...now lets note a few subtle differences in the statblock...
Move 15 translates to 40 ft.
Damage: 5d8. We could simply bump up the damage, or, thanks to its Intelligence granting it feats, take Improved Natural Attack as a bonus feat.
Int: High translates to an Intelligence score of 13-14. A horned devil's mental ability scores are Int 14, Wis 18, Cha 22, so this fits nicely. Shall we just use those mental stats?
Other things we might borrow from the cornugon...
Special Qualities: Damage reduction 10/good and silver, immunity to fire and poison, resistance to acid 10 and cold 10, regeneration 5, see in darkness, spell resistance 28, telepathy 100 ft.
Skills (as inspiration for which skills it should take): Bluff +24, Climb +28, Concentration +24, Diplomacy +10, Disguise +6 (+8 acting), Hide +21, Intimidate +26, Listen +22, Move Silently +23, Search +20, Sense Motive +22, Spot +22, Survival +4 (+6 following tracks)
Feats (as inspiration for which feats it shoudl take): Cleave, Improved Sunder, Iron Will, Multiattack, Power Attack, Weapon Focus (spiked chain)
Spell-Like Abilities: At will—dispel chaos (DC 21), dispel good (DC 21), magic circle against good, greater teleport (self plus 50 pounds of objects only); persistent image (DC 21) 3/day—fireball (DC 19), lightning bolt (DC 19). Caster level 15th. The save DCs are Charisma-based.
Fear Aura (Su): A horned devil can radiate a 5-foot-radius fear aura as a free action. A creature in the area must succeed on a DC 23 Will save or be affected as though by a fear spell (caster level 15th). A creature that successfully saves cannot be affected again by the same horned devil’s aura for 24 hours. Other devils are immune to the aura. The save DC is Charisma-based.
Stun (Su): Whenever a horned devil hits with a spiked chain attack, the opponent must succeed on a DC 27 Fortitude save or be stunned for 1d4 rounds. The save DC is Strength-based. This ability is a function of the horned devil, not of the spiked chain.
Infernal Wound (Su): The damage a horned devil deals with its tail attack causes a persistent wound. An injured creature loses 2 additional hit points each round. The wound does not heal naturally and resists healing spells. The continuing hit point loss can be stopped by a DC 24 Heal check, a cure spell, or a heal spell. However, a character attempting to cast a cure spell or a heal spell on a creature damaged by a horned devil’s tail must succeed on a DC 24 caster level check, or the spell has no effect on the injured character. A successful Heal check automatically stops the continuing hit point loss as well as restoring hit points. The check DC is Constitution-based.
Regeneration (Ex): A horned devil takes normal damage from good-aligned silvered weapons, and from spells or effects with the good descriptor.
See in Darkness (Su): All baatezu can see perfectly in darkness of any kind, even that created by a deeper darkness spell.