I don't think that you will be able to use Pay With Miles in combination with the Companion Certificate. Two reasons:
1. The primary and companion tickets both have to be purchased using your American Express Card, I don't think that using PWM would be possible.
2. I think that PWM is only available online, and the companion tickets still have to be booked via the phone number on the certificate (unless things have changed.

As for cheap fares. I've sometimes been able to find fairly inexpensive (sub $300) fares between SEA, PDX or other fairly good-sized west coast cities (e.g. SFO, SAN, and SMF) and either TPA or SRQ. I don't have experience with the other markets that you are looking into, although I suspect that the other reasonably-sized markets in Florida (MCO, maybe RSW, FLL, and MIA), will have similar fares, but the smaller airports in WA may not be as good a bet for cheap fares. Lately I've found the best fares between 4 and 6 weeks out. Good luck.