Hi,
CELTA, like TESOL and TEFL certificates are an asset, but in South Korea, the Department of Immigration requires a 4 year BA minimum. Universities and Colleges generally require a Master's Degree. At least for hagwons you also have to produce other documentation.
As I recall Japanese Immigration also requires at least an undergraduate degree.
Whatever you do, try to avoid working in Ulsan, South Korea. There are some serious work place problems in that area. For more information, read the earlier postings on this page and on the School Reviews page as well, about the hazards of working in Korea if you happen to sign a contract with a less than reputable school.