I knew he was going to be there, and sure enough, he was there.
Assuming one follows the "rules", a parenthetical phrase should be set off by commas. Plus two sentences joined by "and" should have a comma ahead of the "and".
The problem is that one would normally consider "sure enough" to be parenthetical -- you can write "I knew he was going to be there, and he was there", and it makes sense, suggesting that "sure enough" is unnecessary and should be considered parenthetical. But you failed to use a comma between "and" and "sure" to mark the start of the parenthetical phrase. Without the comma the reader must work harder to parse the sentence.
By these criteria you should add a comma between "and" and "sure".
However, "and sure enough" is something of a set phrase/idiom, and one could argue that, as such, the meaning is easily recognized and the comma is not required (especially since, in normal speech, a pause before "sure" would probably not occur).
It's something of a judgment call.