There is a typo in the Atmel datasheet, the rise time for the 100kHz case should be 1000ns, not 100ns (it would not need to be lower than the 400kHz case of 300ns) then you get:
\$\dfrac{1us}{400pF} = 2.5k\Omega \$; for the 100kHz case
The LCD datasheet (almost certainly) means the maximum bus capacitance, not the capacitance that it adds to the bus. It probably adds around 10pF. You can either check with an LCR meter or just set it up with a 2k resistor and look at the rise times.
Many devices don't fully comply with the official 400kHz specs, so it's best to refer to these for understanding the conditions under which 400kHz can work (bus capacitance, pullup/current source/etc) See section 6 onwards in particular (for example see note 4 on pg.47:
[4] In order to drive full bus load at 400 kHz, 6 mA IOL is required at 0.6 V VOL. Parts not meeting this specification can still function, but not at 400 kHz and 400 pF)
Further on, these tables are pretty helpful, and look to agree with your calculations:
Seems like just a line omission from the datasheet. On the Pin Description section of Page 6
Pin 5- SDA:
Serial Data Input/Output. SDA is the data input/output for the I2C serial interface. The SDA pin is open drain and requires an external pullup resistor. The pullup voltage can be up to 5.5V regardless of the voltage on VCC.
Pin 6- SCL:
Serial Clock Input. SCL is the clock input for the I2C interface and is used to synchronize data movement on the serial interface. The pullup voltage can be up to 5.5V regardless of the voltage on VCC.
It seems to just skip a line stating that the pin is open drain and requires the external pull up, but then adds the same line afterwards, stating the pull up value. Looking at older versions of the datasheet, back when Maxim Integrated was Maxim-Dallas and even just Dallas Semi, the omission has always been there.
That said, the typical wiring diagram has always been correct, showing the pull up needed on both i2c lines, as the i2c standard requires.
As for the SQW/Out pin, the Pull Up is only required if you are using the line. It can be disabled in the rtc's settings (Or should I say, comes disabled, needs to be turned on). Having a pull up resistor on the line, when you are not going to use it, will waste energy, needlessly draining a battery (Slowly) in battery applications. As the datasheet says, this can be left floating, i.e. no pull up, if not needed. The Adafruit device breaks it out for your convenience if you do want to use it, but you need to add the pull up externally if you want to (or use the Arduino's internal pull-up option)
Best Answer
The correct pullup resistance for the I2C bus depends on the total capacitance on the bus and the frequency you want to operate the bus at.
The formula from the ATmega168 datasheet (which I believe comes from the official I2C spec) is --
$$\text{Freq}<100\text{kHz} \implies R_{\text{min}}=\frac{V_{cc}-0.4\text{V}}{3\text{mA}}, R_{\text{max}}=\frac{1000\text{ns}}{C_{\text{bus}}}$$
$$\text{Freq}>100\text{kHz} \implies R_{\text{min}}=\frac{V_{cc}-0.4\text{V}}{3\text{mA}}, R_{\text{max}}=\frac{300\text{ns}}{C_{\text{bus}}}$$
The Microchip 24LC256 specifies a maximum pin capacitance of 10pF (which is fairly typical). Count up the number of devices you have in parallel on the bus and use the formula above to calculate a range of values that will work.
If you are powering off of batteries I would use values that are at the high end of the range. If there are no power limits on the power source or power dissipation issues in the ICs I would use values on the lower end of the range.
I sell some kits with an I2C RTC (DS1337). I include 4K7 resistors in the kit which seems like a reasonable compromise for most users.