Creo lo siguiente para truncar una cadena en Java a una nueva cadena con un número dado 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;

Esto es lo primero que se me ocurrió, y sé que podría mejorarlo. Vi otra publicación que hacía una pregunta similar allí, pero estaban truncando cadenas usando los bytes en lugar de String.substring. Creo que preferiría usar String.substring en mi caso.

EDITAR: acabo de eliminar la referencia UTF8 porque preferiría poder hacer esto también para diferentes tipos de almacenamiento.