First, a word about what a phoneme is: a phoneme is "a sound" which a language uses as one of its primitive elements for constructing utterances. For instance /p/ in "paper, spit". It turns out that there are physical differences between the three kinds of p in those words, and those physical differences are excluded when coming up with the list of phonemes of a language. In other words, a phoneme is an abstraction from actual speech, omitting certain kinds of differences. Also note that this is about pronunciation and not spelling, so "rough, fish, phylum" all contain the phoneme /f/. Some examples of phonemes in English are /p, b, t/. Some physically-different sounds that exist in English which are not phonemes include [k kʰ kʲ kʲʰ], that is, these are physical variants of a single phoneme, /k/. (They are called "allophones"). Some examples of phonemes in Hindi are /p pʰ b bʰ/. English physically has p and pʰ, but there is a rule telling you when you use one versus the other, so the difference is not primitive. English simply does not have bʰ. A list of phonemes is always "in language X".
A "pair of phonemes" would then be "any two phonemes in the language". For example /f, s/ or /m, æ/. The notion of "pair of phonemes" is not a useful notion in language, since it is arbitrary. However, there are some kinds of "pairs of phonemes" that could be useful, for example the three pairs /d, n/, /b, m/, /g, ŋ/ exemplify English sounds which differ in a single, unified way (presence of absence of nasal airflow).
If by "pair of phonemes" you mean "any two-member subset of the set of phonemes in language X", then it follows that "all pairs of phonemes exist". Since /bʰ/ is not a phoneme in English, /p, bʰ/ is not a pair of phonemes in English – we fail on the "phonemes in language X" criterion. This definition of "pair of phonemes" is constructive – you can always construct all of the two-member subsets of any set containing more than 1 element. You may want to know that all languages have at least 2 phonemes.
So, "No, by definition".
OTOH, if the question is about sequences of phonemes in a specific order, then the trick is to find really low-frequency (of occurrence) sounds, and scanning the grammars of languages that have such sounds. Clicks are low frequency of occurrence. In no language with clicks do you ever find two consecutive clicks. That's probably a sample problem arising from the extreme rareness of clicks.