Note that Wikipedia should not just rename the wiki, it should still maintain a domain name alias for preserving links to Wikipedia from other sites.
This means that the two domains will have to be supported, even if "zh-min-nan" becomes an alias in interwiki prefixes, and as CNAME alias in the DNS. And these aliases will need to be preserved for long (Interwiki prefixes could be fixed, but there are tons of templates and pages to change before this becomes possible).

So the first step is to add the domain name alias as a CNAME and make sure that the wiki server accepts this hostname (it requires a reconfiguration of the webserver itself, then adding a CNAME aliasing of "nan.*" to "zh-min-nan.*" to test that the web server accepts both host names, then chaning the DNS again to reverse the CNAME aliasing, then adding the interwiki prefix aliasing, and reconfiguring all other wiki servers to support the new prefix).

This done, we'll be able to start the cleanup of templates, and some bots may work at fixing the interwiki links spread on lots of pages for each wiki. For templates this cannot be made safely by a bot.

As a small step here, wgLanguageCode was fixed in bug 34866.

I support the renaming, because zh-min-nan is not a "prefixed" language code. nan is more natural.

Although I would not get rid of the zh-min-nan, but make it an alias for nan.