What you're trying to do is definitely doable with just Synergy. Synergy has configuration options to send different keystrokes to each server. If it were me, I'd make the Linux machine the Synergy server and the Windows machine the client. I recommend this simply because the Synergy docs tell you how to edit the config file manually to do things like:

[code:1]
# When meta is pressed on the server, send alt to the client
meta = alt
[/code:1]

and/or:

[code:1]
# When super+f12 is pressed on any screen, send super+L to machine "larry" and control+alt+delete to machine "curly"
# (which pretty much describes what you want to do, I think.)
keystroke(super+f12) = keystroke(super+L,larry), keystroke(control+alt+delete,curly)
[/code:1]

or:

[code:1]
keystroke(f6) = keystroke(f6,larry), keystroke(z,curly)
[/code:1]

Check out:

http://synergy2.sourceforge.net/configuration.html

You can probably also do that with the Windows machine as the Server using the 'HotKeys' section of the configuration window, but I've never used that, and the documentation on how to do that I couldn't immediately find.