The answer to the first part of the question, in general, is no. Consider the following counter-example: let $\mathscr{D}(\mathbb{R}^{kd})$ be the complex vector space of (complex-valued) smooth functions with compact support on $\mathbb{R}^{kd}$ (seen as functions $f(x_1,\ldots,x_k)$ with $k>0$ arguments in $\mathbb{R}^d$), and define $$ \mathfrak{A}=\mathbb{C}\oplus\bigoplus^\infty_{k=1}\mathscr{D}(\mathbb{R}^{kd})\ ,$$ whose elements have the form $$\underline{f}=(f_0,f_1,f_2,\ldots)\ ,\quad f_0\in\mathbb{C}\ ,\,f_k\in\mathscr{D}(\mathbb{R}^{kd})\ (k>0)$$ with $f_k=0$ for all but finitely many $k$. This vector space over $\mathbb{C}$ becomes a $*$-algebra if we endow it with the product $$\underline{f}\underline{g}=\left(f_0g_0,\,\ldots,\sum^k_{j=0}f_j\otimes g_{k-j},\,\ldots\right)$$ and the involution $$\underline{f}^*=(\bar{f_0},\,\ldots,\,f_k^*,\,)\ ,$$ where $$(f_j\otimes g_l)(x_1,\ldots,x_{j+l})=\begin{cases} f_0g_l(x_1,\ldots,x_l) & (j=0) \\ g_0f_j(x_1,\ldots,x_j) & (l=0) \\ f_j(x_1,\ldots,x_j)g_l(x_{j+1},\ldots,x_{j+l}) & (j,l>0) \end{cases}$$ and $$f_k^*(x_1,\ldots,x_k)=\overline{f_k(x_k,\ldots,x_1)}\ .$$ In this case, the element
$(0,0,f\otimes g+f'\otimes g',0,\ldots)$, where $f,g,f',g'\in\mathscr{D}(\mathbb{R}^d)$ are linearly independent, cannot be written in the form $\underline{h}^*\underline{h}$ for any $\underline{h}\in\mathfrak{A}$, for the same reason the sum of the tensor products of linearly independent vectors does not factorize. Of course, $\mathfrak{A}$ is not a C$*$-algebra, although it is a topological $*$-algebra. In general, one considers the cone generated by the positive elements (or the latter's closure in the topological case). This contains only positive elements in the case of C$*$-algebras thanks to the spectral theorem for self-adjoint elements, which does not hold in the above example.