The Stack Overflow podcast is back! Listen to an interview with our new CEO.
3 of 5 added 1 characters in body

What about the following code. I've improved it by not using regular expressions (except one call of String.split, perhaps you already improved this by your own function split).

public static String replaceVariables(final String expression, final Map<String, String> vars) {
    final StringBuffer sb = new StringBuffer();
    String tmpExp = expression;
    int firstIndex = tmpExp.indexOf('$');
    int lastIndex = -1;

    while (firstIndex != -1) {
        sb.append(tmpExp.substring(0, firstIndex));

        if (tmpExp.charAt(firstIndex + 1) == '{') {
            lastIndex = tmpExp.indexOf('}', firstIndex);

            if (lastIndex > -1) {
                final String group = tmpExp.substring(firstIndex + 2, lastIndex);
                final String parts[] = split(group, ',');
                sb.append(vars.get(parts[0]).substring(0, (parts.length == 1 ? parts[0].length() : Integer.valueOf(parts[1]))));
                tmpExp = tmpExp.substring(lastIndex + 1);
            } else {
                sb.append(tmpExp.substring(firstIndex));
                return sb.toString();
            }
        } else {
            sb.append('$');
            tmpExp = tmpExp.substring(firstIndex + 1);
        }

        firstIndex = tmpExp.indexOf('$');
    }

    sb.append(tmpExp);

    return sb.toString();
}

With the following example values:

final String expression = "Hello! This is a ${1} ${0,2} of foo bla.";
final Map<String, String> vars = new HashMap<>();
vars.put("0", "Foo");
vars.put("1", "funny");

I have a benchmark of (1 million replaces):

// Original (yours):  1981 ms
// Improved (mine):    594 ms

So it's a bit more than three times faster than your implementation. And the more values like {1,3} are in the input expression, the faster it is in relation:

Input:

final String expression = "${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ${1} ${0,2} ";

Benchmark:

// Original: 17809
// Improved: 3043

So, here it is more than five times that fast!

Probably, it can be much more improved. But I just wanted to show you a possible direction so far!