What runtime complexity if DNF formula not PAC-learnable, $O(2^N)$ or $O(2^{2^N})$ runtime?
There's a misconception here.  PAC learning doesn't require the learning to find the shortest formula.  It merely requires the learner to find any formula that has sufficiently low generalization error.  If there are multiple formulas that meet that criteria, the learner is allowed to output any of them -- not necessarily the shortest.

Take a closer look at the formal definition, and hopefully you'll see how that follows from the definition.