O motd do Ubuntu é gerado executando os arquivos em /etc/update-motd.d/ .
No meu sistema 14.04, a mensagem *** System restart required *** parece ser gerada pelo script 98-reboot-required , portanto, para adicionar suas mensagens personalizadas, você deve criar um script com um número menor que 98 e executá-lo ou fazer um eco Quaisquer mensagens que você queira. Não esqueça de tornar seu novo script executável.
Referência: link