Whenever I try to start the game, it loads for a few moments but then tells me "Shadow Man (EFS) is damaged and can't be opened. You should move it to the Trash", I just hit cancel.

What the heck do I do about this? I am quite stumped

Thanks for the link, I did read the support first, but I failed to notice there were separate support articles for each game.

The first solution did not work, but the second one (disabling the annoying Mac Appp Store security) worked perfectly :)

Interesting. Good thing I posted the link. I almost did a copy/paste of the first solution instead.