The UAC star may well be awarded for the number of enemies killed. When I *ahem* accidentally set off the Trigun's nuke, I killed everything up to that point - I died well before Cybie, but I got the UAC Star, bronze cluster. So it might be for 100% kills on a certain difficulty.
The Hell Champion medal would obviously be awarded for winning in the arena...
But if we do take the UAC star to mean 100% kills... Hm, my first win netted me, as well as the star, an Aurora and Prejudice medal. Theory: Prejudice for killing the Cyberdemon, while Aurora for using a BFG to do it? Or something relating to the BFG, perhaps...
This bears further investigation, I believe.