I would recommend updating the NUC BIOS here: Intel® Download Center
Also, if possible, try different SSD on your NUC.
Let us know if another SSD has worked for you, as I can see you have returned the Samsung 850 EVO.
I did return Samsung 850 EVO M.2 and instead installed Intel SSD 530 series - 180 GB SSDSCKGW180A401. The Intel SSD M.2 worked perfectly, recognized in BIOS and by Win8.1 install USB flash drive. Now going thru process of setting up NUC as HTPC. Not sure what the deal is with Samsung 850 EVO, because I made no changes in BIOS for the Intel module to work.
I am glad you got this computer working with Intel SSD. It might be some type of compatibility issue with the EVO drive.