Many thanks for the latest comments from Brothers Corion and Oshalla. As shown below I now have a solution that:
1. Moves the insertion point to a set of character(s);
2. Adds a wingding symbol after the character(s)
3. Removes the target string
I looked again at my conversion from a word macro to Perl and made changes.
Eventually I found something that worked! The following lines, find the target character(s), move the insertion point just after and then add the wingding symbol.

$selection->Find->ClearFormatting;
$selection->Find->{Text} = "*";
$find_exec_res = $selection->Find->Execute;
$move_res = $selection->MoveRight ( {Unit => wdCharacter, Count => 1} 
+);
$selection->InsertSymbol( { Font=> "Wingdings", CharacterNumber => -40
+62, Unicode => 1 });
[download]

The search moves forward through the document and therefore will fail if the second target
character is before the first. However, I found that the following moved the insertion point to the
start of the document (perhaps not very elegantly but it works).

$selection->MoveLeft ({Unit => wdCharacter, Count => 9999});
$selection->MoveUp   ({Unit => wdLine, Count => 9999});
[download]

I believe that there is an option as part of the ‘Find’ that allows you to set the replacement character(s) but I have not made this work as yet.
However I can use the code I already have to remove the target character(s) after I have added the wingding symbol.
I have found that the inserted wingding takes on the target characters characteristic’s such as height and colour.
If there is more than one character in the target string the move is still one character.
On my version of Word (2007) I find that the four ‘symbol’ fonts of wingdings, wingdings 2, wigding3 and webdings have the same ‘mapping’ between the number required in InsertSymbol line and their ASCII value.
The number required is ASCII number – 4096.
I hope this may help anyone else who is trying to modify a word document with Perl.