Windows 10 is different. It is by design. This is the way Microsoft does business because previously people were not following Microsoft's licensing terms. Meaning the licence terms stated that you can't transfer Windows from one computer to another if it had an OEM license. An OEM license is the Windows license on a branded computer with Windows preloaded. That license was supposed to be used only on the original computer. People didn't follow this in practice by using the printed key on a different computer. So with Windows 10 Microsoft did away with the printed key. Now you would be forced to do what they've said from the onset of previous versions. You may feel it is your license to do as you please but it isn't. If you want a license to with as you please then you needed to have bought a retail Windows license and not an OEM license that ships with computers.
The store that helped you did you a disservice if they cloned your old computer onto the new one. Especially when they say that "this" issue with licensing "sometimes" happens. They know better and they are doing the wrong thing. They should have sold you a new license with the new computer. And they may very well have sold you that new OEM license but by transferring things the wrong way they messed up the licensing on the new computer.
If you still have the old computer running there may be a way to get the old license product key that the store that helped you said was impossible to find. I haven't tried this but it might be worth trying.
https://www.intowindows.com/how-to-view-your-windows-10-product-key/If this doesn't work then I suggest doing some testing with a spare hard drive. Remove existing hard drive from new computer. Install spare hard drive. Install Windows 10 via flash drive. Prepare this flash drive on another computer using the Windows Media Creation Tool from Microsoft. Test installing Windows 10 Home. Give it a test run. If the licensing issue is fixed then the new computer has a valid Win 10 Home license. You won't need the key. They key is either in the firmware or Microsoft will recognize your new computer once it connects to the Internet and link the key to it that was registered for it when the computer was built. Windows 10 is easier to deal with reinstalling Windows from scratch because the license is in the cloud. Microsoft has a sort of a digital fingerprint of your hardware in the cloud. So you can reinstall without needing to enter the key.
My opinion is that Windows 10 is better than any version prior. Even before with previous versions of Windows, cloning a hard drive from one computer to another was never a good idea as a lot of baggage was brought over. A new computer is the perfect opportunity to start fresh. So cloning is always bad.
So if cloning is bad how do you do it? Well the computer store should have backed up your data only. Then fresh installed Windows on the new computer. Then fresh installed all your programs. Then reconfigure said programs and restore just data. More work but perfect results every time and no baggage from old computer. And no licensing issues.