guys. I also live in the middle east and I couldn't find Heavensward on PSN via PS4. but if you search in https://store.playstation.com. you can find it!
I did pay for it from the website and I got an option to start downloading to my playstation and it automatically started the download.

just make sure you are in the store corresponding to your account