Google attempts to do this by letting you stumble upon commands, but I don't think that is good enough. I don't think tutorials are either, but I don't have any solid alternatives.
Like if you ask Google Now "Can you help me set a reminder", it prompts you for details. That isn't discoverable per se, but it addresses a lot of the same problems, the user only has to understand that the system can answer questions about capabilities to have that conversation.
If I also use something that doesn't have a shortcut 3 times within the programs running then it asks me if I want to set a shortcut for that action.
I think as time goes on Google will eventually be on this route considering how well it works (at least with the first portion of showing the shortcut command whenever I use it).
However that still wouldn't solve the problem of the users having to learn the commands from scratch first so if they don't know it exists they would never learn the shortcut for it in "OK Google"
The only down side is it's not great on looks but honestly it's a popup to tell you a shortcut so it fits well for the purpose
"Key promoter"
I wonder if we have to pass through all design stages every time something changes.
[1] https://www.gnu.org/software/emacs/manual/html_node/emacs/M_...
This is particularly frustrating with regard to my parents and their Android phones. I'll get them set on how to do something... and then it suddenly no longer works, anymore.
For a gang of kids or twenty-somethings who are constantly communicating about the tech in their hands, this... word of mouth / osmosis approach to adoption may work.
For many others, it's damned frustrating. Including for the techie family members who end up having to help them -- over and over and over...
The conversational UI in text adventure games was fun to explore because the fall backs were sometimes funny.