Those buses leave from the little bus station at Chunghsiao Fuhsing. Look for a little place with a bunch of benches inside. It’s on Fuhsing just outside and down a bit (in the same block) from the MRT exit. I know they go to Taichung,so might be worth your while to wander over there and find out if they go all the way down the Island. I understand it takes six hours from Taipei to Kenting but don’t know the cost.
There are a few places around Taipei where you can catch the coaches you mentioned. Not too sure if any run to Taipei, but it is easy enough to go to Kaohsiung and catch another bus from there.
I recommend the Aloha bus company as the most luxurious. Chengde Road, just north of Taipei Main Station, is where a number of bus companies operate from.
We once took one of those buses behind Taipei Main Station, and it took 6 hours to get down to Kenting. But when we stupidly decided to come back on a Sunday morning (11:00) it took more than 11 hours to reach Taipei, with only one rest stop. Not so amusing.
How much does it cost to fly?