I should have thought of that! You need to delete the old value each time:

Sub addpercent()
    Dim osld As Slide
    Dim shpSN As Shape
    Dim strPercent As String
    For Each osld In ActivePresentation.Slides
        strPercent = " (" & CStr(Round((osld.SlideIndex / ActivePresentation.Slides.Count) * 100, 1)) & "%)"
        osld.HeadersFooters.SlideNumber.Visible = True
        Set shpSN = getSN(osld)
        If Not shpSN Is Nothing Then
             With shpSN.TextFrame.TextRange
             .Text = ""
             .InsertSlideNumber
             .InsertAfter " of " & ActivePresentation.Slides.Count & strPercent
             End With
        End If
    Next osld
End Sub
 
Function getSN(osld As Slide) As Shape
    For Each getSN In osld.Shapes
        If getSN.Type = msoPlaceholder Then
            If getSN.PlaceholderFormat.Type = ppPlaceholderSlideNumber Then
                Exit Function
            End If
        End If
    Next getSN
End Function