And yes, all of them do have to be done in All-Star. I think you're thinking of the point system in combat trials that unlocks further trials, I always did them all on All-Star right off the bat, so I hardly noticed. I do remember gaining Goal RP on each of my characters for completing them on all 3 difficulties, though.
WOW! I started the combat trials, but realized you don't get any points if you lose which is fine for the easier ones, but for the harder ones it's faster to level up just by playing versus. I should go through more fo the acrades though. Hey, if I just beat an arcade on hard, does that automatically give me the trial for beating it one normal too?