Not necessarily. The particular style can have an arbitrarily long description, and learning will still work as long as the class of described rules is small.
Fixed overheads are ignored in the definition of Kolmogorov complexity.
A "particular style of baroque elaboration" is simply a program through whose eyes certain rules look short, which look elaborate and baroque through the eyes of another program.
The PAC-learning scenario doesn't have any parameter that goes to infinity, so I'm not sure why you dismiss "fixed" overheads :-)
I declare this Open Thread open for discussion of Less Wrong topics that have not appeared in recent posts.