I am sorry to hear you experience an issue with downloading the companion app. There are not any specific restrictions related to a particular phone model, and therefore I am not sure why you cannot get the app on your device. Is there any error that occurs if you wait a bit? Is this the same case on other Windows Phones as well? Can you search for and install other apps successfully?
Would you try downloading the app from the App Store
directly? This worked on my side on all the devices I tested on.