Ответ. $k = 100400$.

Обозначим числа на окружности через $a_1, \dots, a_{2009}$, и положим $a_{n+2009} = a_n = a_{n-2009}$. Пусть $N = 100400$.

1. Положим $a_2 = a_4 = \dots = a_{2008} = 100$ и $a_1 = a_3 = \dots = a_{2009} = 0$. Пусть мы сумели сделать все числа равными при каком-то значении $k$. Рассмотрим сумму $S = (a_2 - a_3) + (a_4 - a_5) + \dots + (a_{2008} - a_{2009})$. Эта сумма увеличивается на $1$ при прибавлении единицы к паре $(a_1, a_2)$, уменьшается на $1$ при прибавлении к паре $(a_{2009}, a_1)$ и не изменяется при всех остальных операциях. Поскольку исходное значение $S$ равно $S_0 = 100 \cdot 1004 = N$, а конечное должно быть нулем, то пара $(a_{2009}, a_1)$ увеличивалась хотя бы $N$ раз. Это значит, что $k \ge N$.

2. Осталось показать, что при $k = N$ требуемое всегда возможно. Рассмотрим произвольный набор чисел $a_i$. Увеличим каждую пару $(a_i, a_{i+1})$ ровно $s_i = a_{i+2} + a_{i+4} + \dots + a_{i+2008}$ раз. Тогда число $a_i$ превратится в
$$a_i + s_{i-1} + s_i = a_i + (a_{i+1} + a_{i+3} + \dots + a_{i+2007}) + (a_{i+2} + a_{i+4} + \dots + a_{i+2008}) = a_1 + \dots + a_{2009},$$
то есть все числа станут равными. С другой стороны, $s_i \le 1004 \cdot 100 = N$, что и требовалось.