The error you report indicates that you're trying to boot with the "Windows Recovery Environment (loader) (on /dev/sda2)" or "Windows 8 (loader) (on /dev/sda3)" entries. Those entries are both suitable for BIOS-mode Windows installations, but you've clearly got an EFI-mode installation. Thus, you should be using the "Windows UEFI bootmgfw.efi", "Windows Boot UEFI loader", "Windows UEFI recovery bootmgfw.efi", or "Windows Boot UEFI recovery" entries. (Probably the first of those.)
If none of those entries work, then something is wrong. In this case, I recommend you download the USB flash drive or CD-R version of my rEFInd boot manager, prepare a medium with it, and boot to that medium. You should be able to boot to both Windows and Ubuntu with rEFInd. If this works, install the Debian-package version of rEFInd in Ubuntu. The computer should then boot to rEFInd when you reboot, and you can use rEFInd as your default boot manager. rEFInd tends to be much less finicky about booting Windows than is GRUB, so using it instead of GRUB as your primary boot manager often fixes problems like this.