Claro, isso vai imprimir o que você pede:
printf '%s\n' "${Array[@]//__SingleQuote__/\'}"
Mas, como você solicita um novo array com os valores corrigidos, use:
ConvertedArray=( "${Array[@]//__SingleQuote__/\'}" )
Naturalmente, os índices de ConvertedArray serão numéricos de 0 para cima. Isso parece não ser um problema, mas desde que você mencionou nos comentários (em outra resposta) continue lendo.
Matriz esparsa
Se a matriz é definida como:
$ Array=( [2]="Mary" [5]="had a __SingleQuote__little__SingleQuote__" [8]="lamb" )
Em seguida, o array é esparso (tem alguns buracos):
$ declare -p Array
declare -a Array=([2]="Mary" [5]="had a __SingleQuote__little__SingleQuote__" [8]="lamb")
Para resolver isso, você precisa de um loop:
$ for i in "${!Array[@]}"; do
> ConvertedArray[i]="${Array[i]//__SingleQuote__/\'}"
> done
$ declare -p ConvertedArray
declare -a ConvertedArray=([2]="Mary" [5]="had a 'little'" [8]="lamb")
e
$ printf '%s\n' "${ConvertedArray[@]}"
Mary
had a 'little'
lamb