The paladin enters the first square of the threatened area. Nothing happens. The paladin continues his move into the second square of the threatened area. Rat gets AoO. Paladin will most probably stop his movement now. Rat gets readied action.
What I think is mostly unlikely here is the fact, that the rat is hidden still, when the paladin moves THAT close to it.