Diese Fehlermeldung erscheint eigentlich nur dann, wenn unterschiedliche Office-Versionen (auch Office-Einzelkomponenten) parallel auf einem Rechner betrieben werden - wobei es deutlich häufiger dann zu diesem Fehler kommt, wenn zuerst die neuere Version installiert wird.
Deinen Informationen zufolge kann dies aber nicht auf eine falsche Installationsreihenfolge liegen, da du zuerst Office 2010 (inkl. der Komponente Visio 2010) hattest, bevor du Visio 2013 aufspieltest.
Die Meldung ("..wird konfiguriert...") weist darauf hin, dass Visio 2013 der Auffassung ist, noch Einträge in der Registry vornehmen zu müssen - obwohl es auch nach Abbruch dieses Vorgangs auch ohne diesen Vorgang funktioniert.
Abhilfe könnte ein Zusatz in der Registry bringen, durch den Visio diesen Vorgang gar nicht erst startet.
Rufe mal die Registry auf und begebe dich auf folgenden Schlüssel:
HKEY_CURRENT_USER\Software\Microsoft\Office\14.0\Word\Options
In der rechten Fensterhälfte der Registry einen Rechtsklick vornehmen -> Neu -> DWORD.
Nun diesen neuen DWORD-Eintrag umbenennen in: NoReReg
Jetzt Rechtsklick auf NoReReg -> Ändern. Es öffnet sich nun ein kleines Fenster. Dort den Wert von 0 auf 1 ändern.
Anmerkung: Da Word eine zentrale Funktion innerhalb des Office-Paketes hat, nehme diese Registryänderung dort vor. Erst, wenn das dennoch nicht hilft, auch unter diesem Registryschlüssel die gleiche Änderung vornehmen (beachte die neuere Version - 15.0):
HKEY_CURRENT_USER\Software\Microsoft\Office\15.0\Visio\Options
Gruß
Shrek3