Since build 1511 (around last december) windows 10 installs would accept win7/8 keys through clean install from bootable media.
If you lack that, you can get the download tool for iso/dvd/usb from MS: just check that the version (32 or 64 bit) and language of current windows matches the new one. (I believe you can change windows 10 language freely after install)
https://www.microsoft.com/en-gb/software-download/windows10
Thus as long as you have windows 7/8/8.1 license key, you should be set. (write it down if you are missing the sticker)
Only case when you would need to buy new windows10 license is if the old windows 7/8 license was activated on different hardware (pretty much tied to motherboard) If it is activated now before upgrade attempts, it should be fine after boot/clean install also.