I just tested on mine:

Right click game in steam, add shortcut to desktop double-click shortcut, game runs.

I checked the shortcut to see what the command is (right-click, properties):

steam steam://rungameid/648800

Is that what you have? The only thing I can think of is that steam isn’t in your path, ie when you double click the shortcut it tries to run ‘steam’ but then can’t find it.

If you open a terminal and type:

which steam

what’s your output? You should have something like /usr/bin/steam