The way I combine that stuff is still a little bit of work, but I don't think it's too bad.

First, yes, you select both and Poly > Combine like you said. Then, what I do, is point snap the vertices together at the edges. If you have a lot of verts, this can take a little while....

Once you have them all snapped together, you can select ALL the vertices (even other vertices that you DON'T want to merge) and go to Edit Poly > Merge Vertices > Options. In the options, set the slider to .0001 and apply. This will make only vertices that are snapped together merge together, while leaving the rest alone.

Still a little bit of work, but this is how I do it.