This code should get you started. It is relatively easy to delete all shapes from a document so you should be able to find examples online easily enough.
Code:
Sub AddRandomBorder()
Dim aRng As Range, i As Integer, aPara As Paragraph, aShp As Shape
Dim iWidth As Integer, iHeight As Integer
With ActiveDocument.Sections(1).PageSetup
iWidth = .PageWidth - 40
iHeight = .PageHeight - 40
End With
For Each aPara In ActiveDocument.Paragraphs
Set aRng = aPara.Range
aRng.Collapse Direction:=wdCollapseStart
If aRng.Information(wdActiveEndPageNumber) > i Then
Set aShp = ActiveDocument.Shapes.AddShape(Type:=1, Left:=20, Top:=20, _
Width:=iWidth, Height:=iHeight, Anchor:=aRng)
With aShp
.Line.ForeColor = RGB(Rnd() * 255, Rnd() * 255, Rnd() * 255)
.Line.Weight = 3
.Fill.Transparency = 1
End With
i = aRng.Information(wdActiveEndPageNumber)
End If
Next aPara
End Sub