Solution:

Let $S = \sum_{i=1}^{k} (a_i + b_i).$ The $2k$ chosen elements are distinct positive integers, so $S \ge 1 + 2 + \cdots + 2k = k(2k + 1).$ The $k$ sums are distinct integers at most $2009,$ so $S \le 2009 + 2008 + \cdots + (2010 - k) = \frac{k(4019 - k)}{2}.$ Combining, $$k(2k + 1) \le \frac{k(4019 - k)}{2} \implies 4k + 2 \le 4019 - k \implies k \le \frac{4017}{5} = 803.4,$$ so $k \le 803.$

To achieve $k = 803,$ take the pairs $(i,\, 1206 + i)$ for $1 \le i \le 401,$ whose sums are the even numbers $1208, 1210, \ldots, 2008,$ together with the pairs $(a,\, a + 403)$ for $402 \le a \le 803,$ whose sums are the odd numbers $1207, 1209, \ldots, 2009.$ The elements used are $1$–$803,$ $805$–$1607$ with no repeats, and all $803$ sums are distinct and at most $2009.$

The maximum is $k = 803.$