In numerous references on noncommutative geometry, one can find some sort of "dictionary" for translating concepts on the topological/geometric side into their corresponding algebraic counterparts (and vice versa). Here is one such example from Elements of Noncommutative Geometry:
My question is: what exactly is the role played by completeness on the topological side? The algebraic side is described in terms of a $C^\ast$-algebra, which is complete in the norm topology by definition, but what happens if we have something like a $C^\ast$-algebra less completeness?
You seem to be a bit confused here. The dictionary goes between spaces (on the left) and algebras (on the right). $C^*$-algebras live on the right side while completeness is a property of the space and so it would live on the left side. So in this respect the completeness of the $C^*$-algebra doesn't come in to play. In fact, since completeness is not a topological property (it is a uniform property) it doesn't fit nicely into the left-hand side either.
For example, $(0,1)$ and $\mathbb{R}$ are homeomorphic and thus have isomorphic corresponding $C^*$-algebras while one is complete and the other is not.
Finally, you're question seems to also be getting at the question of what can we do with non-complete algebras.
While I'm not an expert in non-commutative geometry, as far I know one often looks at dense subalgebras of $C^*$-algebras, which are non complete. The motivation here is that when one puts additonal structure on the topological space (like for example a smooth structure) you want the collection of functions to preserve this structure (so look at smooth functions and not all continuous functions). This amount to looking at a subset of the original $C^*$-algebra and thus restricting attention to the dense sub-algebra described above.