FM-index and pattern search with wildcards
You are correct that w* is already addressed by fixed-substring search.  I'll give some pointers on general regex search; most text indexes can be searched for variable patterns with a bit of extra work.

First, backwards search is a consequence of the fact that the FM index and most full text indexes use suffix sorting with the most significant digit on the left, because virtually no one thinks in terms of prefix sorting with the MSD on the right.  If the latter were used the FM index would use forward search; it's simply a product of the choices made when setting up the data structure.   Another fact to note is that regex's can be reversed, so any pattern in the forward direction can be reversed and applied using backward search. 

Search with wildcards is not hard to do, but it requires multiple branches through the wildcard matches, which must be searched through some sort of tree-traversal strategy, with backtracking and so on. This paper describes pattern-matching on Patricia trees for instance.  

It's not that different from searching sequential text; in the FM index case you can always find the characters immediately preceding the matches found so far and determine if they match the pattern correctly.