It turns out that I have figured it out. Here is a full solution.
Suppose that the hypotheses on $ R $ in the second definition hold. Let
$$
I_{A} \stackrel{\text{df}}{=} \{ a \in A \mid (a,0_{B}) \in R \} \quad \text{and} \quad
I_{B} \stackrel{\text{df}}{=} \{ b \in B \mid (0_{A},b) \in R \}.
$$
Claim 1: $ I_{A} $ and $ I_{B} $ are closed two-sided ideals of $ A $ and $ B $ respectively.
Proof of Claim 1
As $ R $ and $ A \times \{ 0_{B} \} $ are $ C^{*} $-subalgebras of $ A \times B $, we see that $ R \cap (A \times \{ 0_{B} \}) $ is a $ C^{*} $-subalgebra of $ A \times B $ also. Then as $ I_{A} $ is the image of $ R \cap (A \times \{ 0_{B} \}) $ under the projection $ * $-homomorphism
$$
\pi: A \times B \to A,
$$
it follows that $ I_{A} $ is a $ * $-subalgebra of $ A $. To conclude that $ I_{A} $ is a closed $ * $-subalgebra of $ A $, which would make it a $ C^{*} $-subalgebra of $ A $, use the well-known fact that any $ * $-homomorphism from one $ C^{*} $-algebra to another has a closed range.
It remains to show that $ I_{A} $ is a two-sided ideal of $ A $. To begin, let $ a \in I_{A} $ and $ x \in A $. By the hypotheses on $ R $, there exists a $ b \in B $ such that $ (x,b) \in R $. Then as $ R $ is a subalgebra of $ A \times B $, we obtain
$$
(a x,0_{B}) = (a,0_{B}) (x,b) \in R \quad \text{and} \quad
(x a,0_{B}) = (x,b) (a,0_{B}) \in R.
$$
Therefore, $ a x,x a \in I_{A} $, and as $ x $ is arbitrary in $ A $, we deduce that $ I_{A} $ is indeed a closed two-sided ideal of $ A $.
A similar argument works to show that $ I_{B} $ is a closed two-sided ideal of $ B $. $ \quad \blacksquare $
Claim 2: $ A / I_{A} $ and $ B / I_{B} $ are isomorphic $ C^{*} $-algebras.
Proof of Claim 2
Define a map $ \Phi: A / I_{A} \to B / I_{B} $ by
$$
\forall a \in A: \quad
\Phi(a + I_{A}) \stackrel{\text{df}}{=} b + I_{B},
$$
where $ b $ is any element of $ B $ such that $ (a,b) \in R $ (such a $ b $ must exist). We now establish the following:
- $ \Phi $ is well-defined. Let $ (a,b),(a',b') \in R $, so that $ (a - a',b - b') \in R $. Furthermore, suppose that $ a - a' \in I_{A} $, i.e., $ (a - a',0_{B}) \in R $. Then
$$
(0_{A},b - b') = (a - a',b - b') - (a - a',0_{B}) \in R,
$$
so $ b - b' \in I_{B} $.
- $ \Phi $ is injective. Let $ (a,b) \in R $, and suppose that $ b \in I_{B} $, i.e., $ (0_{A},b) \in R $. Then
$$
(a,0_{B}) = (a,b) - (0_{A},b) \in R,
$$
so $ a \in I_{A} $.
- $ \Phi $ is surjective. Given any $ b \in B $, the requirements on $ R $ guarantee that there exists an $ a \in A $ such that $ (a,b) \in R $. Hence, $ \Phi(a + I_{A}) = b + I_{B} $.
This concludes the proof of Claim 2. $ \quad \blacksquare $
Claim 3: The required $ C^{*} $-algebra $ C $ is $ B / I_{B} $.
Proof of Claim 3
Define a surjective $ * $-homomorphism $ f: A \to B / I_{B} $ by $ f \stackrel{\text{df}}{=} \Phi \circ q_{A} $, where $ q_{A} $ is the quotient map from $ A $ to $ A / I_{A} $. Similarly, define a surjective $ * $-homomorphism $ g: B \to B / I_{B} $ simply by $ g \stackrel{\text{df}}{=} q_{B} $, where $ q_{B} $ is the quotient map from $ B $ to $ B / I_{B} $.
Let $ (a,b) \in A \times B $.
- If $ (a,b) \in R $, then
$$
f(a) = \Phi({q_{A}}(a)) = \Phi(a + I_{A}) = b + I_{B} = g(b).
$$
- Conversely, if $ f(a) = g(b) $, then by the same relations above, we have $ \Phi(a + I_{A}) = b + I_{B} $. From the definition of $ \Phi $, there exists a $ b' \in B $ satisfying $ (a,b') \in R $ such that $ b + I_{B} = b' + I_{B} $. Hence,
$$
(a,b)
= (a,b') + \underbrace{(0_{A},b - b')}_{\text{$ \in R $, as $ b - b' \in I_{B} $}} \in R,
$$
which concludes the proof of Claim 3. $ \quad \blacksquare $
