Te recomendaria que usaras un array:
String hexValues = "0123456789ABCDEF";
y accedieras con complejidad constante a los valores del array concatenandolos directamente con "+".
De esta forma puedes hacerlo con un unico bucle for y es posible que ganes bastante en velocidad. Pasas de complejidad O(n^4) a O(n). Ademas, creo que la funcion toHexString es bastante pesada.