How can I get the first part of the API Deployment URL from inside cloud formation template?
Did you try the variable ServerlessRestApi? It works for us like this:

Outputs:    
    EncryptURL:
      Description: "Encrypt endpoint URL for Stage environment"
      Value: !Sub "https://${ServerlessRestApi}.execute-api.${AWS::Region}.amazonaws.com/Stage/encrypt"