Speaking as an ex-paxil user (discovered that I was actually happier without!), I know that it is available here in Taiwan. If you have a full time job and health card, you can get Paxil (known here as Paroxetine) much cheaper than in the U.S.
Here’s a listing for a psychiatrist in Kaohsiung (I’m sure there are others, too):
Psychiatry
Dr. Ming-Jen YANG
Tel: (07) 731-7123, ext. 8750
Kaohsiung is a big, polluted city, not much different from the other cities in Taiwan. The big draw is the bar/pub scene, although some enjoy the proximity to Kenting, a pleasant beach area. Try this page to learn more about Kaohsiung: