The best time to look for a job at a Korean University is between June and August or December to February. Your qualifications, look fine. If you're worried about not having any esl experience, I reccomend doing a summer camp in Sout Korea, they usually begin in July. If not, just talk up the teaching prac you did on your CELTA if your employers have any reservations.
I like the Koreans and thier ways. They are not ashamed to be true to thier culture and traditions. The food is great, you just need to drop all your preconceived notions of how food tastes to really enjoy it. The countryside is stunning, and if you make the effort to respect Korea and learn about thier culture you will find them the loveliest most hospitable people on the planet. The only problem with Korea is the droves of Canadian ESL teachers that roam the country, stay away from them they will make you negative. Good Luck.