For the record, the highest point in Utah is about 13,500 feet.

The main problem with dogs in cold weather & snow is keeping them warm and protecting their feet. I have no personal experience with dog boots, but I have read that they can cause more problems than they cure. Like with people, they need to fit well or there will be sores. I have a fleece vest for my dog, which he wears well. But it isn't that much protection. I also have a sleeping bag and pad for him, but I doubt it would be good much below freezing.

I would suggest starting with short dayhikes in good weather and work up from there. Maybe do an overnighter where you have the option of bailing out if problems arise.