At a high enough level of sophistication you can just have conversational help.

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.