Your excellent Steyr will certainly kill a deer or an elk. Most people lean toward heavier bullets for elk, so you might investigate the 180gr loads. The SSG '04, IIRC, weighs upwards of ten pounds empty. This is heavier than I'd personally like for an active style of hunting, but will work fine for hunting from a stand.
I'm ambivalent about carrying a "backup" handgun. When I have a rifle in my hands - a vastly more effective weapon than any pistol - I really see little need for a pistol. Some guys do like it for a coup de grace that damages less meat than a second rifle shot, but I think a lot of guys just feel cool and swanky carrying a pistol. It's 2-3 pounds of extra weight that might be better spent carrying something more useful out in the wild - especially if you're already carrying a heavy rifle. Your Smith .357 would work fine as a sidearm, if you do wish to carry one.
I've never hunted Utah, and so can't comment on the expense. You might take a look at the Utah Fish and Game web site to get an idea of cost for non-resident hunting permits and the like.