You need to start a wrapper shell, like this:
Exec=bash -c "notifiy-send \"$(command)\""
Note: Don't miss the double quotes around $(command)
What makes in your case:
Exec=bash -c "notifiy-send \"$(service http restart)\""
Or if the user need to authenticate use gksu
:
Exec=bash -c "notifiy-send \"$(gksu service http restart)\""