The builtin printf in bash has a special format specifier (i.e. %b) which converts \x** to the corresponding value:
$ str='foo%20%5B12%5D'$ printf "%b\n" "${str//%/\\x}"foo [12]
Finally, thanks to #bash IRC channel, I found a "not so bad" solution :
echo `echo string%20with%5Bsome%23 | sed 's/%/\\\x/g'`