Given an algebra $A$, one can ask whether it has a unit. If one exists, one then shows it is unique: $1_A = 1_A1_A' = 1_A'$. Thus being unital is a property of an algebra and not extra structure. Either an algebra has a unit or it does not.
Similarly, given a complex $*$-algebra $A$, one can ask whether there exists a C${}^*$-norm on $A$, i.e., a norm on $A$ which satisfies the following properties:
- $A$ is complete in this norm,
- $\|ab\|\leq \|a\|\cdot\|b\|$ for all $a,b\in A$, and
- $\|a^*a\|=\|a\|^2$ for all $a\in A$.
If one exists, then one shows that it is unique; the norm is determined by the spectral radius as the OP point out: $$ \|a\| = \|a^*a\|^{1/2} = r(a^*a)^{1/2} \qquad\forall\, a\in A. $$ (The spectral radius only equals the norm for normal elements, and the C${}^*$-axiom does the rest.) Thus being a C${}^*$-algebra is a property of a complex $*$-algebra and not extra structure. Either there exists a C${}^*$-norm or there does not.
So how might one go about determining whether a complex $*$-algebra admits a C${}^*$-norm? When it is unital (or after one unitizes), as the OP suggests in the first bullet point, it suffices to look at the spectral radius and ask whether it gives a C${}^*$-norm. The following exact statement was pointed out to me by Andre Henriques.
A unital complex $*$-algebra $A$ is a C${}^*$-algebra if and only if the function $\|\cdot\|: A \to [0,\infty]$ given by $$ \|a\|^2 := \sup\left\{ |\lambda| : a^*a - \lambda 1_A \text{ is not invertible}\right\} $$ is a C${}^*$-norm on $A$.
Another way is to find a faithful $*$-representation $\pi$ from $A$ into another C${}^*$-algebra $B$ whose image is norm closed. Then $\|a\|:= \|\pi(a)\|_B$ works.
Often in my own work, I will have a finite dimensional unital complex $*$-algebra and need to know if it is a C${}^*$-algebra. Here are a couple conditions that work in the finite dimensional setting.
Suppose $A$ is a finite dimensional unital complex $*$-algebra. The following are equivalent.
$A$ is a C${}^*$-algebra.
For all $a\in A$, $a^*a=0$ implies $a=0$.
$A$ is $*$-isomorphic to a unital $*$-subalgebra of $M_n(\mathbb{C})$ for some $n\in \mathbb{N}$.
There exists a linear functional $\varphi:A \to \mathbb{C}$ such that $\varphi(a^*a) \in (0,\infty)$ for all $a\neq 0$, i.e., $A$ has a faithful positive linear functional.
An outline for a proof of 2 implies 1 can be found as Exercise 3.1.27 in these notes I wrote for a course on quantum algebra. A proof of 3 implies 1 can be found as Theorem 3.2.1 in Vaughan Jones' notes on von Neumann algebras. That 4 implies 3 follows by performing the GNS construction for $(A,\varphi)$.
