One cannot write k | n + k | m. Indeed, k | n is not a number; it is either true or false depending on whether k divides n. Addition is not defined on Boolean values (true and false). Instead, you could write, "Since k | n and k | m, we have k | (mq) and therefore k | (n - mq)".

The conclusion k = p does not make sense to me either. Your proof showed that every common divisor (not just GCD) of n and m is a also a common divisor of m and r and vice versa, i.e., the sets of common divisors of (n, m) and (m, r) are the same. Therefore, the maximums of these sets are also the same, i.e., the gcd(n, m) = gcd(m, r).

More generally, call r a linear combination of n and m if r = an + bm for some integers a and b. So, if r is a linear combination of n and m, then every common divisor of n and m is also a divisor of r. Similarly, if r and p are two linear combinations of n and m, then every common divisor of n and m is also a common divisor of r and p. Therefore, if r, p are linear combinations of n, m and, vice versa, n, m are linear combinations of r, p, then gcd(n, m) = gcd(r, p). Now, if n = mq + r, then m = 0 * n + 1 * m and r = 1 * n + (-q) * m are linear combinations of n and m. Conversely, n and m are linear combinations of m and r. By the claim above, their GCDs are the same.