There are no direct connections between North Korea and either Japan or South Korea, but it is of course possible to visit North Korea starting in either of the two other countries.
From Pyŏngyang, there are only direct flights to a handful of cities in China and Russia: Beijing, Shanghai, Shenyang and Vladivostok. In addition, there are international trains from Pyŏngyang to Beijing and Moscow. New Zealand citizens may transit without a visa in Beijing, Shanghai and Shenyang for up to 72 hours and within that time also leave the airport. Flying to Pyŏngyang from Japan or South Korea through any of the three Chinese cities should be no problem.
To get a visa for North Korea, you must have booked an organized tour from any of the North Korean tourism operators. They offer both group tours and individual tours, but since you will be accompanied at all times by North Korean guides, individual tours are relatively expensive. Most group tours include flight or train to and from Beijing, but if you book an individual tour, you are likely to be able to choose yourself how to get to Pyŏngyang.
Usually, the North Korean visa is arranged by the tour operator and will be given to you before departure in Beijing. For individual tours, you can also apply for a tourist visa at a North Korean embassy, providing that you have a booking confirmation from the tour operator. I am not sure if the application process is that fast everywhere, but the North Korean embassy in London is said to issue tourist visas within 20 minutes.