These days I cook all my meals on the gas grill on the back porch.  Even
in the winter.
I grill steak, pork and such.  Except bacon and eggs, I do that on a
electric griddle.

To cook salmon I put the slab of salmon filet, boneless,
scale side down, on a double layer of
aluminum foil, then fold the edges up about an inch to
keep the drippings
from getting in the grill.  Put a chunk of butter on top of
the fish (yes, I know
butter is not paleo).  Then close the lid of the grill.  Let it
cook about 20 minutes
or until it seems done.  You can experiment with time here.
Then put the whole thing on a wooden board, drip on
some lemon juice, some salt, and enjoy.

The reason I use aluminum foil instead of a metal tray is because
my wife HATES the smell of fish.  So I cook it outside, and
eat it quickly, then fold up the foil and put it right
into the garbage can
with the lid tightly on.

Other ideas: Sprinkle on some dried onion flakes before cooking.
Sprinkle on some sage or dill before cooking.

R. Keene