Recently I've had to deal with this issue too - mistakenly installed Office2013 with a used Product Key.
After looking through half of these answers I gave up and fixed the problem myself - most people who say "this is easy, just change it in control panel" are probably not even talking about the same product - they are most likely using the corporate version
of Office 2013, instead of Office 2013 Home and Business. If they'd taken the time to read some of the previous posts they'd have realised 20 other people have already posted the exact same thing, now that's 20 more unhelpful posts we have to look through
before finding a useful one.
The suggestions to use the command line may be likely to work, but I feel that there's got to be a simpler way to do this. I'm an IT professional and comfortable with using the command line, but not everyone would be.
I did look through more posts later and found that the "online repair" posts may hold promise, but by that time I had already fixed the problem and didn't need to try it.
I think my solution to this is probably the simplest and easiest method.
Just re-install Office 2013 without uninstalling - using the same media or file you used in the first place. It would ask you for the product key again - this time enter the correct product key.
The install would then continue but notice that it completes very quickly compared to the first time you installed it.
After it finishes, if your new product key is valid then it will even activate itself automatically.
And don't worry about having 2 installs as it only updates the first install rather than duplicating it.