Coding theory and complete problems
An answer to the first question can be found in a paper by Schaefer and Umans, Completeness in the polynomial-time hierarchy: A compendium (2002).

In subsection "Coding and cryptology" (see p. 24), two $\Pi_2^p$-complete problems appear: checking an upper bound on the covering radius of a linear code, and deciding whether a linear code is $r$-identifying ($r$ part of the input). A certain $\Sigma_3^p$-complete problem called "Minimum block decoder" can be found on p. 28 (see also $\Sigma_2^p$-complete "Minimal block encoder and decoder", p. 25).

I guess following the references should help in digging out more related problems.