If bash is available on that system:

LC_ALL=C find /path/to/share -depth -name '*:*' -type d -exec bash -c '
  for file do
    base=${file##*/}
    mv -i "$file" "${file%/*}${base//:}"
  done' bash {} +

Should remove the :s in the names of directories.

If bash is not available, but mksh (MirBSD shell, and also the shell of Android) or ksh93 is (that ${var//pattern/replacement} operator is actually from ksh93), that should also work if you replace bash with ksh above. Same with zsh.

If bash is available on that system:

LC_ALL=C find /path/to/share -depth -name '*:*' -type d -exec bash -c '
  for file do
    base=${file##*/}
    mv -i "$file" "${file%/*}${base//:}"
  done' bash {} +

Should remove the :s in the names of directories.

If bash is not available, but mksh (MirBSD shell, and also the shell of Android) or ksh93 is (that ${var//pattern/replacement} operator is actually from ksh93), that should also work if you replace bash with ksh above. Same with zsh.

Beware that if both /path/to/share/foo:bar and /path/to/share/foobar directories exist, mv -i /path/to/share/foo:bar /path/to/share/foobar will actually move foo:bar into foobar. With the GNU implementation of mv, that can be avoided by passing the -T option to mv in which case you will get (thanks to -i) a mv: overwrite '/path/to/share/foobar'? prompt instead, and if you answer yes and foobar was empty, foo:bar will be renamed to foobar (and the old foobar discarded).