Comme de bien entendu is a set expression built a similar way than these other idiomatic ones:

• comme de coutume
• comme de juste
• comme si de rien n’était
• plus que de raison.

It is indeed used to emphasize bien entendu.

De role is, according to the TLFi,

II.− De marque une relation syntaxique; il est introducteur de subst., de pron. ou d’inf. en fonction de compl., de suj., d’attribut, d’appos., ou en fonction expressive.
…
B.− [De introducteur de suj., d’attributs, d’appos.; de signifie « le fait de », en parlant d’un fait particulier.]
2. De + attribut
a) De + attribut du suj.
…
− Dans des gallicismes
ε) Comme de juste, comme de raison, comme de vrai, (fam.); comme de bien entendu, comme de sûr (pop.). Comme cela est juste, de raison, vrai, bien entendu, sûr. Je lui payerai sa peine, comme de raison (Staël, Lettres div.,1793, p. 475). Pour lui, « le général », c’est l’général Anselme!… Pas, Chalumeau? − Comme de sûr ! répondit le planton (Gyp, Souv. pte fille,1927, p. 141).

It can hardly be replaced by comme bien entendu. The latter cannot end a sentence and otherwise, comme is used to start a subordinate clause while comme de bien entendu is itself a full subordinate clause.

Comme, bien entendu, ce n’est pas de votre faute, nous prendrons la réparation sous garantie.

As of course it’s not your fault, we take the repair under warranty.

Comme de bien entendu, le parking est payant alors je suis venu en bus.

Needless to say, the car park is not free so I came by bus.

I never heard tout comme bien entendu without commas. Otherwise its usage is slightly different, e.g.:

Tout comme, bien entendu, les pneus avant, il a aussi fallu changer les pneus arrière.

Just like, obviously, the front tires, the rear ones also had to be replaced.