Is there a rule, or at least a pattern I could remember, when deciding whether to use こく or ごく for 国？
天国 = てんごく
全国 = ぜんこく
At first I thought perhaps an ん before こく would cause it to rendaku to ごく, but in the 全国 example this is not the case!
Any tips for remembering the distinction?
This isn’t at all an absolute rule, but it’s quite uncommon for 連濁 to occur twice in a row. Try googling ‘rendaku tofugu’. There’s an article on some of the general patterns. Ultimately though, even if you remember it for this pair, I don’t think there are any foolproof rules that will allow you to predict pronunciations for everything, so you’ll just have to get a feel for it through experience.
Do you mean as an explanation for why ぜんこくisn’t ぜんごく? Just to be clear, the ぜん part isn’t rendaku, because it’s not… continuing anything. That’s just how it is. The definition of rendaku is the changing of something from unvoiced to voiced that comes after another sound.
But I guess you’re saying that rendaku is unlikely to occur if there was already something voiced earlier.
Good point. I hardly use the term 連濁, honestly. Should have realised from the kanji used that it literally means ‘link muddy’ and so can only refer to the phenomenon of a sound becoming voiced when one word is connected to another. Guess I should have said 「濁点」 rarely occur twice in a row.
But yes, so, you got what I meant. Thanks for helping me use the term correctly.
At least on WK, it’s only ごく for the following:
Out in the wild, you’re on your own. 
Went through all the words on Jisho that end in 国, and these are the only ones that are read as ごく:
And also the following derived phrases:
So, bottom line, if in doubt, it’s fairly safe to assume こく. Except for when it’s くに／ぐに.
That is above and beyond. Bravo, sir.
Did you check what the Rendaku script has to report about it?
It may have some general rule that applies here ?
The script reports exactly what alo already mentions. There’s just 3 ごく countries in Wanikani: heaven, China and neighboring country.
Because of similar information on rendaku’d 所, I’m very happy with this particular script 
Good call linking it here.