Quando você executa um comando ssh remotehost some_command type, seu $PATH pode não ser definido para os valores esperados.
Por exemplo, podemos ver que o PATH no meu shell de login atual não corresponde ao PATH remoto, mesmo que eu esteja fazendo login na mesma máquina:
$ echo $PATH
/home/sweh/bin:/usr/local/bin:/usr/bin:/usr/local/sbin:/usr/sbin:/u/bin:/usr/local/bin:/usr/bin/X11:/etc:/usr/local/sbin:/sbin:/usr/sbin
$ ssh localhost 'echo $PATH'
/usr/local/bin:/usr/bin
Por esse motivo, é normal especificar o nome completo do caminho para os comandos.
Nesse caso, a mensagem de erro Cannot run program service: no such file or directory significa que o comando pkexec foi encontrado (provavelmente está no PATH padrão), mas o comando service não foi.
Então, especifique /sbin/service ... eg
ssh [email protected] "pkexec /sbin/service iptables restart"