I don't think the rules are clearly defined, so here's my attempt to clarify them (though
Masem is the final arbiter, of course :), it sounds like we assume that $h and $f are already set, and so don't count that assignment, though we do count the assignment of the 'decoration character class'.
So following what I think are the rules (subject to clarification), here's my try weighing in at 96 characters:
$j=-1;print" "x(--$h),map({$_==1?"*":rand()<$f?(qw(0 @ * +))[rand 4]:"
+="}1..($j+=2)),$/for 1..$h
Update: Curses! foiled again :-)
Though japhy's reply does lead to this 87 character answer:
$j=1;print$"x--$h,($_-1?map rand>$f?"=":qw(0 @ * +)[rand 4],1..($j+=2)
+:"*"),$/for 1..$h