Without regards to the actual case and the particular countries
involved, I am wondering how it is even possible that a court in one
country orders the whole another country to do something, let alone
when the two countries do not even formally have diplomatic relations.
The main statute that is relevant in the U.S. is the Foreign Sovereign Immunities Act (FISA) of 1976. In general foreign states are immune from liability in U.S. courts (and most courts of the developed world) subject to certain exceptions, the most common of which are as follows:
Foreign state waives its immunity explicitly or implicitly
Commercial activities by foreign state in or directly affecting the United States Property taken in violation of international law is at
Rights in U.S. property acquired by succession or gift or rights in immovable property situated in the United States are at issue
Money damages are sought against a foreign state for personal injury, death or damage to or loss of property caused by its tortious
act or omission, occurring in the United States
Enforcement of an arbitration agreement made by the foreign state with or for a private party
Money damages are sought against a foreign state for personal injury or death that was caused by an act of torture, extrajudicial killing,
aircraft sabotage, hostage taking or their support, if the foreign
state is a designated sponsor of terrorism
Admiralty lawsuit to enforce a maritime lien against a vessel or cargo of the foreign state, based on commercial activity
The exception above in bold was probably the one applied in the North Korean case. The only countries to which that exception applies are North Korea, Syria, Sudan and Iran. (There are also separate similar rules related to countries with whom the U.S. is in a declared war.)
There is sporadic ongoing constitutional separation of powers litigation in the U.S. over whether a FISA authorized lawsuit can proceed over the objections of the President as expressed by the U.S. State Department. The argument that FISA is unconstitutional in this context is that diplomacy and foreign policy is exclusively an executive branch power to the exclusion of Congress and the judiciary, but for the most part, this extreme position has been rejected in recent years. A conservative U.S. Supreme Court, however, could revisit this question (conservative judges tend to favor more absolute executive branch authority in foreign affairs).
Once a party wins, however, the winner needs to identify foreign assets subject to the jurisdiction of the court from which to collect the judgment, such as gold deposits or U.S. governmental or corporate bonds or ships docked in U.S. ports, owned by the country.
In strong contrast to the case above, the UK media recently overtly
demonstrated disobedience of a New Zealand court name suppression
order: a man arrested in NZ for allegedly committing an appalling
crime was granted temporary name suppression, and that was ignored by
the UK media. I am wondering if there is anything that would stop a
New Zealand court to hold the UK to account just like the US court
just did North Korea.
In the New Zealand case, the remedy would be to bring suit against the particular newspapers or reporters involved, rather than the state. But, the U.K. might not enforce those judgments if those defendants lost, so enforcement might be limited to New Zealand based assets and persons, and then, only if the New Zealand court found that it had jurisdiction over the defendants under New Zealand law. So, this isn't really analogous.
So, in general, are there any internationally recognised
laws/treaties/protocols etc. that define if/when a court in one
country can assert jurisdiction over the whole another country and
hold it to account? Or is that completely up to the court and whatever
extremes it dares to come up with?
See above in the U.S. case. Most countries have similar statutes or case law to FISA which codified the case law applying customary international law at the time that it was adopted.
One example that comes into my mind is the European Court of Human
Rights: if a country signed the European Convention on Human Rights,
it can be held to account by the court. But what conventions, if any,
can be applied to the two cases above?
The European Court of Human Rights case is one of consent to the jurisdiction of an international body by treaty.
Countries like the UK and NZ have statutes or treaties governing when a foreign judgment (e.g. a judgment from a New Zealand court) will be recognized domestically. There are also usually laws governing when people present in one state will be extradited to another, usually in the form of a bilateral treaty between the affected states.