If the maximum Hamming distance $d$ between the keys is small enough (and to a lesser degree if the key size $n$ is bits is small enough), one obvious technique is that Alice computes $H(k_1)=h$ for $H$ some cryptographic hash, e.g. SHA-256; and sends $h$ to Bob. He explores $x$ of small Hamming weight until $H(k_2\oplus x)=h$, and when he finds such $x$, he knows $k_1=k_2\oplus x$. There are $\displaystyle\sum_{i=0}^d{{n}\choose i}$ values to try. That's $2^{\approx40.5}$ hashes for a $n=128$-bit key with up to $d=8$ garbled bits, which is already inconveniently slow/costly for Bob, thus that does not work at all for sizably larger $d\log_2(n)$.
If the key has enough entropy and thus can't be enumerated (e.g. it has $n\ge128$ uniformly random and independent bits) and is used to key some fast cryptographic algorithm unrelated to $H$ (e.g. AES when $H$ is SHA-256), this reveals nothing useful about the key. However, beware of interactions! As an extreme example, if the key is used as an HMAC-SHA-256 key, and $H$ is SHA-256, and $n>512$, then $k_1$ is entirely compromised, because by definition of HMAC for long keys, $\forall M,\,\text{HMAC-SHA-256}(k_1,M)=\text{HMAC-SHA-256}(H,M)$.
Note: this is essentially the question's brute force method, except that by processing the key thru a hash independent of the normal use of the key, we avoid using the key in one of its possible intended later way. A more formal approach could always use $k_1$ as the key of a Key Derivation Function, with one derivation parameter reserved for repairing $k_1$.
If the key is large with aplenty entropy (e.g. 256-bit or more), and the above can't be applied because $d\log_2(n)$ is too large, or we want no guesswork for Bob, another option is to use Forward Error Correction: Alice computes and reveals $C=\text{FEC}(k_1)$ of $c$ bits, with $c$ large enough to correct the expected error knowing $k_2$, but still a small fraction of $n$.
It must be used a FEC system where the message normally sent for payload $M$ is $M\mathbin\|C$ with $C=\text{FEC}(M)$, which is common, and includes some Turbocode (as used in 3G/4G mobile communications). The FEC should have little or no extra error-detection capability after correction.
Alice computes and sends $C\gets\text{FEC}(k_1)$, and $h\gets H(k_1)$ as before.
Bob receives $C$ and $h$, applies the FEC recovery to $C$ and $k_2$ to get a tentative $\widetilde{k_1}$, and if $H(\widetilde{k_1})=h$ concludes that $k_1=\widetilde{k_1}$.
Compared to the previous scheme, at most $c$ bits of entropy have leaked about $k_1$, and for a full-entropy $k_1$, we are safe as long as $n-c$ remains large enough to make $k_1$ unguessable; and the FEC, $H$, and the algorithm used for $k_1$ do not interfere.
If we again allows some guesswork for Bob, we can reveal less about the key, as follows.
Alice
- computes $C\gets\text{FEC}(k_1)$ as above
- optionally applies some public pseudorandom permutation $P$ to $C$, yielding $C'$ (or just $C'=C$)
- splits $C'$ into $C_1\|C_2=C'$, with $C_2$ of $r$-bit, e.g. $r=32$ (or smaller, down to possibly $1$);
- computes $h\gets H(C_2\mathbin\|k_1)$
- sends $C_1$ and $h$
Bob
- recovers $C_1$ and $h$
- for up to $2^r$ values of $\widetilde{C_2}$
- deduces the corresponding $\widetilde{C}=P^{-1}(C_1\mathbin\|\widetilde{C_2})$ (or just $\widetilde{C}=C_1\mathbin\|\widetilde{C_2}$ for no optional pseudorandom permutation)
- applies the FEC recovery to $\widetilde{C}$ and $k_2$ to get a tentative $\widetilde{k_1}$
- if $H(\widetilde{C_2}\mathbin\|\widetilde{k_1})$ matches $h$
- concludes that $k_1=\widetilde{k_1}$, and proceedq to use that with Alice.
- if no match is found, stops with failure.
$C_1$ was $c-r$-bit, thus at most that much entropy has directly leaked. The pseudo-random permutation allows a simple security argument that the attacker's best strategy has cost $O(2^{n-c+r})$ operations for full-entropy $k_1$ even for pathological FEC, but is probably not necessary in practice.
If $k_1$ is not full-entropy, then $O(2^{\text{Entropy}(K_1)-c+r})$ work must remain infeasible to the adversary, and if we want a simple security argument (including if $k_1$ is used only in part), we can pass $k_1$ thru another public PRP before applying the whole scheme, and pass it thru the inverse permutation in the end.
If wanted, the PRPs can be built from a MGF as in OAEP.
