(1) Jane wrote a letter to the restaurant, complaining about the new
This seems to be the most natural, at least in conversation. The "complaining" phrase is close enough to "Jane" such that logical ambiguity arising from its proximity to "restaurant" isn't that significant, especially since it's likely that Jane would complain, and not the restaurant. In other words, it's pretty clear that Jane is the one complaining.
(2) Jane, complaining about the new menu, wrote a letter to the
This is logically unambiguous, in other words clearer than (1), but I see this occurring more in written English than in conversational English.
(3) Complaining about the new menu, Jane wrote a letter to the
Same as (2)
(4) Jane wrote a letter to the restaurant, in which she complained
about the new menu.
No logical ambiguity here, but overly wordy in that there are more concise alternatives, such as (1) to (3) above.
(5) Jane wrote a letter to the restaurant and complained about the new
This is the most "incorrect", as it doesn't express the same thought as (1) to (4). In (1) to (4), "wrote" and "complained" are tightly coupled--Jane complained in the actual act of writing. However, in (5), the "and" between the verbs effectively decouples "wrote" and "complained", making them independent actions.