У sed ще є команда N, яка довантажує наступний рядок у буфер (pattern space), в межах якого здійснюється пошук та заміна. Приблизно уявляю, як можна це зробити циклічно (з використанням міток і переходів), трохи пізніше напишу.

PS виправлено

Почав вчора вдень на роботі щось подібне малювати, але обірвали і не дали.
Тільки я тупішу умову робив — «якщо в цьому рядку нема }, то підтягти наступний».

sed -e ':loop /.*}.*/!{ N ; b loop } ; s/\(\\ukindex{[^/^}]\+\)\//\1!/g'

p.s.А чого у всіх бекслеш один перед ukindex? Він же так що є, що нема. В якомусь  \newukindex{слабка/двоїстість|)}% теж заміну зробить.