A medium size trompe l'oeil is 2000 gp + 500 gp per HD to make. Cheaper constructs that I can think of lack skills.
Mhh, I've given it a look and seems very easily abusable. Personally, I just need 1HD, 1 rank in UMD and, possibly, Additional Traits to make UMD a class skill, but the rules seem way too vague. Nothing that is already pre-made and codified?
Any created servant with the use magic device skill is potentially abusable. Seriously. The question is whether you will abuse it.
The only medium construct with UMD by default that a search found me is the soulbound shell. Since that requires a 12th level spellcaster to sacrifice their life to create it, it's probably impractical for you. Also it's not cheap.
Most constructs have no Int, and so does not get skills. There is the Brain Bioconstruct Modification for a price of 45,500 gp (cost 22,750 gp).
Once it has Int, it can get skills and feats. As you mention you want Additional Traits to get UMD as a class skill. You also want to get Skill Focus and Magical Aptitude as these will get +3/+6 and +2/+4 based on the ranks they have.
Of the traits you can get, there are the following:
Basic (Magic) Dangerously Curious for +1 trait and class skill
Basic (Magic) Mechanical Aptitude for 1/day reroll before success is known
Campaign Adaptive Magic (Reign of Winter) for +1 trait and class skill
Campaign Artifact Hunter (Giantslayer) for +1 trait and class skill
Campaign Skillful (Ruins of Azlant) for 1/day reroll after result known
Region Azlanti Scholar (Ironbound Archipelago, non-elf) for +2 trait on Azlanti stuff
Religion Underlying Principles (Nethys) for +1 trait and class skill
The construct I would make is a Sentient Wax Golem for 14000 gp with a 14 UMD. Next is a Soulbound Mannequin for 16500 gp with a 19 UMD. Last is a Terra-Cotta Soldier for 19500 gp with a 17 UMD.
Angelic Guardian (6HD, 15 UMD, Price:67500, Cost:34750)
Blood Golem (8HD, 17 UMD, Price:68000, Cost:34250)
Carrion Golem (4HD, 11 UMD, Price:56000, Cost:28250)
Caryatid Column (4HD, 11 UMD, Price:62500, Cost:32250)
Caryatid Column (3HD, 10 UMD, Price:57500, Cost:29750)
Chrystone (4HD, 11 UMD, Price:16000, Cost:8500)
Clockwork Mage (15HD, 29 UMD, Price:129500, Cost:65750)
Clockwork Servant (2HD, 6 UMD, Price:53000, Cost:26750)
Clockwork Soldier (8HD, 17 UMD, Price:82500, Cost:41750)
Crystalline Golem (8HD, 17 UMD, Price:51500, Cost:25750)
Emerald Automaton (5HD, 14 UMD, Price:57500, Cost:29250)
Gargoyle Stone Idol (5HD, 14 UMD, Price:84500, Cost:43750)
Golden Guardian (8HD, 17 UMD, Price:78800, Cost:47050)
Graven Guardian (6HD, 15 UMD, Price:64000, Cost:32250)
Hanshepsu (15HD, 24 UMD, Price:46500, Cost:24000)
Ice Golem (6HD, 15 UMD, Price:64000, Cost:32250)
Junk Golem (4HD, 11 UMD, Price:55700, Cost:27950)
Lead Skeleton (10HD, 24 UMD, Price:86500, Cost:44250)
Magnesium Golem (8HD, 17 UMD, Price:72500, Cost:38250)
Mask Golem (4HD, 11 UMD, Price:22500, Cost:12500)
Mirror Man (6HD, 15 UMD, Price:24500, Cost:12500)
Mummy Golem (8HD, 17 UMD, Price:67500, Cost:34250)
Necrophidius (3HD, 10 UMD, Price:53000, Cost:27000)
Petrified Horror (20HD, 34 UMD, Price:155500, Cost:88250)
Rope Golem (6HD, 15 UMD, Price:59700, Cost:29950)
Scarecrow (5HD, 14 UMD, Price:61000, Cost:30750)
Scarecrow (5HD, 14 UMD, Price:61000, Cost:30750)
Sentient Wax Golem (5HD, 14 UMD, Price:14000, Cost:7000)
Sepulchral Guardian (10HD, 24 UMD, Price:86500, Cost:43750)
Soulbound Mannequin (10HD, 19 UMD, Price:16500, Cost:8500)
Soulbound Shell (15HD, 24 UMD, Price:115000, Cost:60000)
Stone Guardian Golem (5HD, 14 UMD, Price:58800, Cost:29800)
Tallow Golem (10HD, 24 UMD, Price:58500, Cost:29500)
Terra-Cotta Soldier (8HD, 17 UMD, Price:19500, Cost:10000)
Toy Golem (6HD, 15 UMD, Price:61500, Cost:31250)
Tribal Totem (9HD, 18 UMD, Price:64500, Cost:32750)
Wax Golem (4HD, 11 UMD, Price:59500, Cost:29750)
Wood Golem (8HD, 17 UMD, Price:62050, Cost:31175)
Wood Golem (8HD, 17 UMD, Price:64800, Cost:31550)
Some are 3pp
Duplicates are due to multiple sources
You can bump Cha +2 for 5000 gp as often as you want.
You can add HD as a proportional price to gain Cha and skills, but is not likely worthwhile.
A Circlet of Persuasion for 4500 will give +3 Comp on UMD.
A Wand Key Ring for 3000 will give +10 insight on a particular spell for scrolls or spell trigger items like a wand.
I think the Circlet is the only magic item worth while.
What spell are you trying to get them to cast (My guess is Disguise Self due to the form requirement)? According to their variants section, Rune Guardian for example doesn't match the type requirements but can be made with any 1st level spell at will. It's cheap enough (3500 to create), small enough and explicitly used to command minions you could have a medium animated object (manikin, costs 2,250 gp to make) wear it and order it around.
Clockwork Mage is worth a mention. 86,000 GP, humanoid and has a built in special wand that gives it a couple of spells (actually cast too, not SLAs).