If all other avenues to fix your issue has failed, then a complete format and clean install is your only option. Like I said previously, check with the linux distro you have for a forum for some answers to your issue.
There are so many questions that can be asked in a situation such as yours.
As now has been mentioned, is one or both installs configured as UEFI. It makes a big difference how the configuration is set.
But since you have done some basic Boot configuration changes, for now I will ask one question. When you go into the bios or open a Boot Device Menu, what options are listed, exactly? If you see one that mentions a "Windows Boot Manger", choose it and boot.
If you don't have any bootable option, a picture of a Diskpart listing from the Command prompt might help us see your situation. Open Diskpart then use a list disk command. Pick the disk number you want to check, probably 0 and type the commands below.
select disk 0
Maybe use a camera and take a picture of the readout.
If you don't have any boot options which lead to Windows, the only other thing I could suggest is using a command to set the boot back to a Windows version. This is only usable on a MBR (Legacy) install and will not help a UEFI install.
Can you comfirm for me that you did a system recovery from a windows 8 (or 8.1) install disc and that has failed?
If the above is true then your windows is gone and I would move on to a fresh install as bassfisher6522 says... in fact, I would also insert a new (blank) hdd first so the old files can be recovered after but perhaps that is outside your budget.