Ah, hai ragione sulla lettera maiuscola iniziale, così il problema dovrebbe essere risolto.

codice:
import java.util.regex.*;

public class regExp {

  public regExp(String str, int repMax) {
    Pattern p = Pattern.compile("[^A-Z]*([A-Z]+[^A-Z]*){"+(repMax+1)+",}");
    Matcher m = p.matcher(str);
    System.out.println(str+" match: "+m.matches());
  }

  public static void main (String[] args) {
    regExp prova = new regExp("asdXPAre1@WQp",5);
    regExp prova1 = new regExp("1aXPArW_sds_OPe1@WQp",5);
  }
}
hai un match se si verifica la condizione espressa nella RegEXP, ossia se ammettiamo che a te interessino solo le stringhe contenenti al più 5 caratteri maiuscoli, vorrai scartare tutte le stringhe con 6 o più caratteri maiuscoli. Allora, devi trovare tutte le stringhe che contengono almeno 6 caratteri maiuscoli e scartarle. Il programmino lì sopra fa proprio quello, anche se puoi pure variare il numero massimo di caratteri maiuscoli che vuoi trovare: ti basta solo invertire il boolean (non l'ho fatto nel programma)