This structure is probably the "best" way to store your data ("best" = what I'm assuming your after, because I'd be perfectly fine with your switch based solution)

1. An EnumMap based solution

EnumMap<Level, EnumMap<Criticality, Priority>> map = new EnumMap<>(Level.class);
EnumMap<Criticality, Priority> c1 = new EnumMap<>(Criticality.class);
c1.put(Criticality.E1, Priority.P1);
..
map.put(Level.C1, c1);
...

Then, simply write this utility method to access the structure:

public static Priority priority(Level level, Criticality criticality) {
    return map.get(level).get(criticality);
}

The advantage of EnumMap is: It offers Map convenience while being rather efficient, as all the possible keys are known in advance, so values can be stored in an Object[].

2. An array based solution

You've already mentioned this, but I'll still repeat the idea, because I've done this in the past, and with proper formatting (that must never be broken by devs, of course), this approach is very readable and not very error prone.

Remember, formatting is key here:

Priority[][] map = {
  //               Criticality.E1   Criticality.E2   Criticality.E3
  // ----------------------------------------------------------------
  /* Level.C1 */ { Priority.P1    , Priority.P2    , Priority.P3    },
  /* Level.C2 */ { Priority.P2    , Priority.P3    , Priority.P4    },
  /* Level.C3 */ { Priority.P3    , Priority.P4    , Priority.P5    },
  /* Level.C4 */ { Priority.P4    , Priority.P5    , Priority.P6    }
};

And now, the method looks like this:

public static Priority priority(Level level, Criticality criticality) {
    return map[level.ordinal()][criticality.ordinal()];
}

In order to prevent failing silently in case someone adds a new enum value in the middle, just add a unit test that asserts the expected ordinal for each enum literal. The same test can also assert the Level.values().length and Criticality.values().length values, and you're safe for the future.

Maybe a Map with a tuple of Criticality and Level as a key?

You could create a key class with a custom equal() and hashCode() method that encapsulate this two values like the following:

public class PriorityTuple{    
  final Criticality c;
  final Level l;

  public PriorityTuple(Criticality c, Level l) {
    this.c = c;
    this.l = l;
  }

  @Override
  public boolean equals(Object o) {
    if (!(o instanceof PriorityTuple)) {
      return false;
    }
    PriorityTuple prioritykey = (PriorityTuple) o;
    return this.c.equals(prioritykey.c) && this.l.equals(prioritykey.l);
  }

  @Override
  public int hashCode() {
    int hash = 5;
    hash = 23 * hash + Objects.hashCode(this.c);
    hash = 23 * hash + Objects.hashCode(this.l);
    return hash;
  }
}

And then create your Map with your entities:

Map<PriorityTuple, Priority> priorityMap = new HashMap<>();

And two methods to simplify add and get:

// add new entry
public static void addPriority(Criticality c, Level l, Priority p) {
  if (null == c || null == l || null == p) return; // if you want some kind of control
  priorityMap.put(new PriorityTuple(c, l), p);
}
// get priority
public static Priority priority(Criticality c, Level l) {
  return priorityMap.get(new PriorityTuple(c, l));
}

Resulting in something like:

addPriority(Criticality.C1, Level.L1, Priority.P1);
addPriority(Criticality.C1, Level.L2, Priority.P2);
addPriority(Criticality.C1, Level.L3, Priority.P3);
addPriority(Criticality.C2, Level.L1, Priority.P2);
addPriority(Criticality.C2, Level.L2, Priority.P3);
addPriority(Criticality.C2, Level.L3, Priority.P4);
// and so on...

// retrieving values...
System.out.println(priority(Criticality.C1, Level.L1)); // print P1
System.out.println(priority(Criticality.C4, Level.L3)); // null if not exist

With this, you can continue add more entries for your enum types in the future without breaking the code (?)