What is your question exactly? You identified the scenario but what you need help with.
If you have an MS 365 subscription then you can just install it on the new machine without any issues.
If you have an older Office 365 license using a product key then install that version again with the same product key. If you don't have the original media anymore AND MS doesn't provide access to it then you'll need to acquire a software version of the product(s) but do not need the license key. If this was part of an OEM purchase then generally the OEM provides download services for getting to the original software. But note that OEMs tend to not allow such software to be transferred to other systems.