Be unique.. start from who.is to make sure that the domain name of the company you want to register is not available.Thats where i started my journey to registering my business. I made sure that the (TLD) xxxxxx.com is not available. This gave me a better chance of securing the name and the domain at the same time... when i went to registra it almost cost me 100/= for name search since i was 99% the name was not available and within 2days i was already registering my business.
Its true that multinational companies some have local tags . Avoid a situation of having  company name like steveholding limited and a domain like this (steve-holding.com ama steveholdingkenya.com) since the simpler domain steveholding.com is not available

Best Regards
Moses