$(...) é um recurso de shell e o comando de atalho do teclado não é executado em um shell.
Tente isso:
sh -c 'notify-send $(fortune)'
Quanto a sh tell-fortune.sh , sem fornecer o caminho completo para tell-fortune.sh , onde sh procuraria?
Quanto a sh ~/tell-fortune.sh , ~ é também um recurso de shell, sem um shell, ele procurará um arquivo no caminho relativo ~/tell-fortune.sh , em que ~ é considerado como -é.