While macropod's answer didn't work, it did get me to the right track and I managed to make the code work. It might not be the most elegant solution, but it does what I need it to do:
Sub FormatTilde()
Set TildeStyle = ActiveDocument.Styles("Approx")
'Start from the beginning of the document
Selection.HomeKey Unit:=wdStory
With Selection.Find
.Forward = True
.ClearFormatting
.MatchWholeWord = False
.MatchCase = False
.Wrap = wdFindContinue
.Execute FindText:="~"
Selection.Style = TildeStyle
Do While Selection.Find.Execute
Selection.Style = TildeStyle
Loop
End With
ActiveDocument.UndoClear
End Sub