Isso ocorre porque o segundo ${param} está dentro de aspas simples, o que significa que ele é interpretado quando o comando é executado por at, que não herdou a variável, pois ela não foi exportada.
Como é uma string vazia nesse ponto, notify-send sai com um erro, pois é necessário um resumo não vazio.
Você pode usar export a uma variável para conter o valor que deseja usar e usar essa variável dentro das aspas simples para obter o valor passado. Ou, como at lê de stdin , você pode simplesmente despejar um script diretamente sem escape estranho, assim:
#!/bin/sh
at now << EOF
notify-send "${param}" "param with value"
EOF