Can I safely delete the Playlist folder I created by Exporting?
Yes. MC does not use it. It is just for exporting for use in other applications.
Does the NAS have to be running MC21? Does it have to be on all the time?
Yes, the NAS will need to be on, or else MC can't back up to it.
If you don't keep the NAS on all the time, you could have MC back up to a different (always on) location, and then copy the files to the NAS when it is on using a syncing application or script.
GoodSync has a nice feature where it can automatically run a sync when a given network drive becomes available. It works well, I use it to sync my "users network share" at work to my laptop's local drive, and it works perfectly (when I walk in and connect the laptop to the work network, it syncs, and it doesn't complain when the laptop is at home or whatnot). So that would be an option.
SyncBack might be able to do the same thing too.
When would backups occurr?
They happen when you start up MC, if it is "time" (based on the last time it was backed up). And, I think, just when it decides it is otherwise idle. And a few other times (such as when you restore another backup, as is noted in the article).
I'm not positive on the details. Mine are kinda all over the place, but often in the early morning (while I'd be sleeping) or mid-morning (when I'd be at work). But it works, and it does it roughly every two days.