А мож не надо усложнять с двойной вложенностью? Накой она нужна?
Меняй тупо по одному - самый надёжный и простой вариант.
str=':D:Dte:Dst (:D)(:D) :Dtest(:D)(:D)(-_-)'
alert(str.replace(/\((:D|-_-)\)/g,'<img src="" alt="$1">'))
Можно конечно сделать как ты хочешь, но не нужно.