Replying to myself, I noticed my NUC now does go to sleep when I got it to leave the HomeGroup.
I'm having now the issue of having it waking from sleep every couple of minutes, it might be due to the wireless keyboard + mouse connected to it. Or woken up by network traffic.
dId you experience this behavior before the installion of W8.1?
Have you tried any of the following methods provided by Microsoft: http://support.microsoft.com/kb/976877/en-us
Can you test another keyboard and mouse on your NUC?
I had my nuc wake up from shutdown straight away most of the time. I thought it was a grounding issue at first. Then I disabled wake on LAN in the bios and that fixed it. Ideally you want wake on magic packet only, but this option isn't in the bios and so needs to be done via the driver options in your OS.