I'm not great at statistics (which is why I try answering these questions sometimes), but here it goes and I'll count on the community to tell me if I'm wrong.
Because I'm not great, I have to break these problems down into small quite elementary chunks.
First, I started with the probability that each side is equal. I believe that that could be expressed as $\mathbb{P}(\text{Both Sides Equal}) = \mathbb{P}(\text{0 Heavy}) + \mathbb{P}(\text{2 Heavy}) \cdot \mathbb{P}( \text{Even Split})$
I decided that that's the probability that you don't choose any heavy coins (thus they must be equal) or that you choose 2 heavies and one is on the left.
I started out by saying that: $\mathbb{P}(\text{0 Heavy}) = \frac{\binom{n - 3}{k}}{\binom{n}{k}}$
After trying to figure out $\mathbb{P}(\text{2 Heavy}) $ I think that I stumbled on this: $\mathbb{P}(i\text{ Heavy}) = \frac{\binom{3}{i}\binom{n - 3}{k - i}}{\binom{n}{k}}$
I also decided that most of the time I wanted to look at selecting both sides at once and then splitting them evenly so I started thinking of $k$ as $2k$.
OK, so that covered $\mathbb{P}(\text{0 Heavy})$ and $\mathbb{P}(\text{2 Heavy}) $, but I had to figure out the probability that given 2 heavies
Thanks to Gerry Myerson, I'm convinced this section was incorrect.
I'd randomly split them evenly between the sides of the scale. I decided I'd flip the heavy coins and if they were heads I'd put them on the left and tails I'd put on the right. That's metaphorically of course. But, basically, there are $2^2$ outcomes of flipping 2 coins and 2 of them result in an even split so $\mathbb{P}(\text{Even Split}) = 2 / 2^2 = 2 / 4 = .5$.
My new thought is that there will always be only 2 ways to have the 2 heavy coins together: both on the left or both on the right. There are $\binom{k}{\frac{k}{2}}$ ways to split the coins. Thus, I think this is correct: $\mathbb{P}(\text{Even Split}) = 1 - \frac{2}{\binom{k}{\frac{k}{2}}}$
If that's correct, I think, the probability of both sides weighing the same is: $\mathbb{P}(\text{Both Sides Equal}) =\frac{\binom{n - 3}{k}}{\binom{n}{k}}+\mathbb{P}(\text{Even Split})\cdot\frac{\binom{3}{2}\binom{n - 3}{k - 2}}{\binom{n}{k}}$
OK. So, the conditions for the left side being heavier than the right side are the same as the conditions for the right side being heaver than the left so $\mathbb{P}(\text{Left Heavier}) = \mathbb{P}(\text{Right Heavier})$.
Thus, I only tried to calculate $\mathbb{P}(\text{1 Side Heavier})$. I spent more time than I'd like to admit before I realized that $\mathbb{P}(\text{1 Side Heavier}) = \mathbb{P}(\neg\text{Both Sides Equal})$.
Nervously, I submit this answer as I run some tests to make sure I'm at least on the right track.