First of all, open Automator. When you're presented with the options sheet, choose Service. After, in the banner of the action, make it say: 'Service takes no input in any application.'
Now, drag in a Run AppleScript action from the Utilities category. Paste the following text in:
on run {input, parameters}
set myAnswer to ((do shell script "defaults read com.apple.finder CreateDesktop") as integer) as boolean
do shell script "defaults write com.apple.finder CreateDesktop " & (((not myAnswer) as integer) as string)
do shell script "killall Finder"
end runNote: this script kills the Finder to finish its job. Remember that if you invoke this during a file operation, bad stuff could happen.
[crarko adds: I tested this, and it works as described.]

