Eu crio o seguinte para truncar uma string em java para uma nova string com um determinado número de bytes.

        String truncatedValue = "";
        String currentValue = string;
        int pivotIndex = (int) Math.round(((double) string.length())/2);
        while(!truncatedValue.equals(currentValue)){
            currentValue = string.substring(0,pivotIndex);
            byte[] bytes = null;
            bytes = currentValue.getBytes(encoding);
            if(bytes==null){
                return string;
            }
            int byteLength = bytes.length;
            int newIndex =  (int) Math.round(((double) pivotIndex)/2);
            if(byteLength > maxBytesLength){
                pivotIndex = newIndex;
            } else if(byteLength < maxBytesLength){
                pivotIndex = pivotIndex + 1;
            } else {
                truncatedValue = currentValue;
            }
        }
        return truncatedValue;

Essa é a primeira coisa que me veio à cabeça e sei que poderia melhorar. Eu vi outro post que estava fazendo uma pergunta semelhante lá, mas eles estavam truncando Strings usando os bytes em vez de String.substring. Eu acho que prefiro usar String.substring no meu caso.

EDIT: Acabei de remover a referência UTF8 porque preferiria fazer isso também para diferentes tipos de armazenamento.