I've added a server in PhpStorm deployment settings but the Tools -> Deployment -> Upload to menu is still greyed out.
You need to specify a deployment path mapping in your server. Even if it's just the root path, you need to enter /. PhpStorm doesn't do it automatically.
Go to your server in deployment settings, click the 'Mappings' tab and enter slash (or your mapping) in the 'Deployment path on server' field. You don't need to enter a web path. Deployment menu should be ungreyed now.