To avoid iterating over string many times to first replace ===abc=== and then ==def== we can iterate over it once and thanks to Matehr#appendReplacement and Matcher#appendTail dynamically decide how to replace found match (based on amount of =).
Regex which can search find both described cases can look like: (={2,3})([a-z]+)\1 but to make it more usable lets use named groups (?<name>subregex) and also instead of [a-z] use more general [^=]+. 
This will give us 
Pattern p = Pattern.compile("(?<eqAmount>={2,3})(?<value>[^=]*)\\k<eqAmount>");
Group named eqAmount will hold == or ===. \\k<eqAmount> is backreference to that group, which means regex expects to find it also == or === depending on what eqAmount already holds. 
Now we need some mapping between == or === and replacements. To hold such mapping we can use
Map<String,String> replacements = new HashMap<>();
replacements.put("===", "<subheading>${value}</subheading>");
replacements.put("==", "<heading>${value}</heading>");
${value} is reference to capturing group named value - here (?<value>[^=]*) so it will hold text between both == or ===. 
Now lets see how it works:
String input = "===foo=== ==bar== ==baz== ===bam===";
Map<String, String> replacements = new HashMap<>();
replacements.put("===", "<subheading>${value}</subheading>");
replacements.put("==", "<heading>${value}</heading>");
Pattern p = Pattern.compile("(?<eqAmount>={2,3})(?<value>[^=]*)\\k<eqAmount>");
StringBuffer sb = new StringBuffer();
Matcher m = p.matcher(input);
while (m.find()) {
    m.appendReplacement(sb, replacements.get(m.group("eqAmount")));
}
m.appendTail(sb);
String result = sb.toString();
System.out.println(result);
Output: <subheading>foo</subheading> <heading>bar</heading> <heading>baz</heading> <subheading>bam</subheading>