Ich schon wieder.
Das Problem konnte nach eigener Recherche gelöst werden.
Für die Nachwelt:
Dieses Problem wird von den eigenen Wordprocessing-Objekten nicht unterstützt. Deshalb muss man auf die Packages zurückgreifen. In diesem Beispiel wird dem Header eine Relationship hinzugefügt auf ein Bild welches bereits im Package liegt:
Dim lHeaderPackage as
PackagePart = headerPart.OpenXmlPackage.Package.GetPart(headerPart.Uri)
Dim lRelation as
PackageRelationship = lHeaderPackage.CreateRelationship(imageUri,TargetMode.Internal, imageRelationType)
Die dabei entstandene Relation.Id kann dann verwendet werden um ein Bild anzuzeigen.