Processes in Microsoft 365 for setting up Office apps, redeeming product keys, and activating licenses.
Are you aware that the licesne terms for Office 2013 have been "improved". Retail licenses for Office 2010 and earlier allowed you to activate on up to 2 computers at the same time, and to transfer those installations to new computers as required.
Retail licenses for Office 2013 allow you to install on only one computer. The license terms have been retroactively changed to allow you to transfer it to another computer if required (the initial license terms in Feb 2013 did NOT allow transfers!)
Question: you say the 2013 key worked. Are you trying to re-install on the same computer or install and activate on a new computer (aka "transfer")?
To Transfer Office 2013:
- you will have to uninstall from the current computer.
- install on the new computer
- activate on the new computer.
You will almost certainly have to do a phone activation (because I expect internet activation to give you precisely the error you are reporting). When you do the phone activation, IGNORE the initial prompts. They too will give you the same error. Instead, wait a LONG time until you are given the option of talking to a live "service" rep. Explain that you are transferring a retail Office 2013 license and have already uninstalled from the previous computer.