At the end of the day, if there are a certain number of jobs in an area, and fewer housing units, then something has to give. What you pay people doesn't even matter. You're just playing musical chairs, and if you pay one group enough to live nearby, you've automatically priced some other group out of the market.
The obvious solution for the firefighters is to pay them well enough to live in the community they protect. Maybe that's a very high salary, but it only seems reasonable that a community that's very expensive to live in will have very expensive firefighters.
But this just pushes the problem elsewhere, since some other set of local workers will now have to live far away. The only real solution is to either build more housing or shed some local jobs.