A creature that, because of the creature's size, provokes attacks of opportunity for entering a foe's square provokes attacks of opportunity when entering that foe's square even if the creature enters that square by taking a 5-ft. step...

The rules cited in the question are from two different places about two different things. The 5-ft. step rules don't care about the creature size rules, and the creature size rules don't care about the 5-ft. step rules. The two rules are managed independently and don't interact. Thus, when a Tiny, Diminutive, or Fine creature enters an opponent's square, it provokes an attack of opportunity even if it entered that opponent's square by taking a 5-ft. step. That's a function of the creature's size exclusive of the creature's 5-ft. step.

Example 1
A Tiny, Diminutive, or Fine creature takes a 5-ft. step when adjacent to opponent and within that opponent's threatened area that doesn't provoke an attack of opportunity (because of the 5 ft. step) and moves into his opponent's square which does provoke attacks of opportunity (because of the creature's size).

When a Tiny, Diminutive, or Fine creature takes a move action to move within its opponent's threatened area then enter its opponent's space, the creature probably should provoke attacks of opportunity twice, once for the movement within the creature's threatened area and once for entering the creature's square, except that the FAQ (see below) says to treat the opportunity granted by moving within a creature's threatened area as part of the same movement needed to enter a creature's space. Thus a typical Medium creature gains only one attack of opportunity against a Tiny foe that takes a move action to enter the creature's square.

Example 2
A Tiny, Diminutive, or Fine creature takes a move action to travel 30 ft. to enter an opponent's square. The creature provokes an attack of opportunity when moving within the opponent's threatened area as normal then can enter the opponent's square with impunity.

It's sort unfortunate that two attacks of opportunity aren't provoked. It might've saved the Dexterity 13 commoner with the feat Combat Reflexes from death by house cat.

...And the FAQ agrees

The Pathfinder Roleplaying Game Core Rulebook FAQ contains the following exchange:

Question: In the section on Tiny and smaller creatures, it says that entering a creature’s space provokes an attack of opportunity, but typically 5-foot steps don’t provoke an attack of opportunity. If a Tiny or smaller creature took a 5-foot step into a creature’s space, would it provoke an attack of opportunity?
Answer: Yes. Even with a 5-foot step, a Tiny or smaller creature entering a creature’s space provokes an attack of opportunity (unless it is using a more specific ability to avoid the attack of opportunity such as the Monkey Shine feat). This doesn’t mean that a Tiny or smaller creature entering a creature’s space and moving out of a threatened square with a move action provokes two attacks of opportunity from that creature, for the same reason that moving out of multiple of a creature’s threatened squares in the same move action doesn’t provoke two attacks of opportunity.

This exchange was added to the FAQ in Jan. 2016.

A creature usually can't take a 5-foot step to enter a square that hampers the creature's movement

When determining the movement costs for hampered movement, the game usually doesn't care where the creature is and instead cares where the creature's going:

Difficult terrain, obstacles, and poor visibility can hamper movement (see Table: Hampered Movement for details). When movement is hampered, each square moved into usually counts as two squares, effectively reducing the distance that a character can cover in a move.

If more than one hampering condition applies, multiply all additional costs that apply. This is a specific exception to the normal rule for doubling.

In some situations, your movement may be so hampered that you don't have sufficient speed even to move 5 feet (1 square). In such a case, you may use a full-round action to move 5 feet (1 square) in any direction, even diagonally. Even though this looks like a 5-foot step, it's not, and thus it provokes attacks of opportunity normally. (You can't take advantage of this rule to move through impassable terrain or to move when all movement is prohibited to you.)

You can't run or charge through any square that would hamper your movement.

Emphasis—and extra emphasis—mine. Thus at issue is the creature's destination square not its current square. The creature's already in its current square, so the creature doesn't have to care about that square's terrain, having already overcome the difficulty of entering it!

For example, going from a square of supernatural darkness into an adjacent square of bright light is just normal movement, but going from a square of bright light into an adjacent square of supernatural darkness usually costs double movement due to poor visibility. In fact, going from any square into an adjacent square of supernatural darkness usually costs double movement due to poor visibility, the condition of the starting square typically not mattering at all.

Exiting then reentering the same square of hampering terrain still costs additional movement, of course. A creature can't move normally back and forth between squares of hampering terrain just because it's occupied the same square of hampering terrain previously. For example, moving from a square of supernatural darkness to a square of supernatural darkness then back to the original square of supernatural darkness does not speed up the return trip.