It's free in the Windows Store (i.e. no license required), you may need to make a Microsoft account to access it, however.
If you install through the Windows Store and are getting that message, you are likely not running an activated Windows 8 copy. The key is stored in the UEFI, so try activating from My Computer > Properties. If that fails, you may need to call.
Microsoft
If your PC is currently running Windows 8 or Windows RT, it's free to update to Windows 8.1 or Windows RT 8.1. And unlike previous updates to Windows, you'll get this update from the Windows Store.