I think this should be it:
!macro _ReplaceFirstByteOccurance _outvar _input _orig _replace
Push $R0 ;max loopcounter
Push $R1 ;loopcounter
Push $R2
!define Lprefix L${__LINE__}
StrLen $R0 ${_input}
StrCpy $R1 0
${Lprefix}Loop:
StrCpy $R2 ${_input} 1 $R1
StrCmp $R2 ${_orig} 0 ${Lprefix}NoMatch
StrCpy $R2 ${_input} $R1
StrCpy $R2 $R2${_replace}
IntOp $R1 $R1 + 1
StrCpy $R0 ${_input} "" $R1
StrCpy $R2 $R2$R0
goto ${Lprefix}End
${Lprefix}NoMatch:
IntOp $R1 $R1 + 1
StrCmp $R1 $R0 0 ${Lprefix}loop
StrCpy $R2 ${_input} ;nothing found, return original string.
${Lprefix}End:
!undef Lprefix
Push $R2
Exch 3
pop $R0
pop $R2
pop $R1
pop ${_outvar}
!macroend
!define ReplaceFirstByteOccurance `!insertmacro _ReplaceFirstByteOccurance`
${ReplaceFirstByteOccurance} $1 $1 ":" "h"
${ReplaceFirstByteOccurance} $1 $1 ":" "m"
StrCpy $1 "$1s"
Learn to use StrCmp/StrCpy/StrLen etc. They're very helpful commands.
Edit2: Doh, can't use $R1 as parameter to a macro that uses $R1, obviously.