Leveling Curve
Let's look at the leveling curve first. The fifth paragraph isn't a typo. The leveling goes something like this:
4th: Minotaur (4), Barbarian (0)
5th: Minotaur (4), Barbarian (1)
6th: Minotaur (4), Barbarian (2)
6.5th: Minotaur (4), Barbarian (3)
7th: Minotaur (4), Barbarian (4)
8th: Minotaur (4), Barbarian (5)
9th: Minotaur (4), Barbarian (6)
9.5th: Minotaur (4), Barbarian (7)
10th: Minotaur (4), Barbarian (8)
At this point the minotaur receives no further bonus levels, because he's received a number equal to half of his CR (i.e. two). Based on this example, it looks like monsters don't receive their bonus levels for levels less than their CR (so the monster doesn't get one between level two and three).
For determining when a monster gains bonus levels, look at the number of levels gained by the party above the monster's CR. In the example the monster is CR 4 so at party level 7 and 10 and extra level is gained, which comes half way through the level. This means that between the 2nd and 3rd party level, and again between the 5th and 6th. For monsters of higher CR this continues every three levels.
Basically when the party level is equal to CR + 3*n -0.5, and n < CR/2, then the monster gains a bonus class level.
(section corrected by Pellanor... Thanks!)
Starting Level
[...] Make sure the group is of a level that is at least as high as the monster's CR. Treat the monster's CR as class levels when determining the monster PC's overall levels.
In your case this means you have a level 5 party (the highest CR).
The Djinn is pretty simple: He's a level 5 Djinn. He's entitled to two bonus levels (half of five, rounded down), which he'll receive at level 7.5 and 10.5.
The Unicorn is entitled to one bonus level, which he'll receive at level 5.5. At 5th level, he'll be a Unicorn 3/ <class level> 2.
The Triton is entitled to one bonus level, which he'll receive at level 4.5. At 5th level, he'll be a Triton 2 / <class level> 4.
The human is the easiest: Humans don't have racial hit dice, so they just use the normal rules.
Experience to Level
This is where things get a little tricky. The rules are phrased in terms of overall party level, which simplifies things a great deal. When you're talking about the level of a specific character, it's more complicated.
In terms of the party, a CR3/Class1 monster fights with a fourth level party. It is effectively a fourth level character in terms of XP. When the party reaches level five, it levels up to CR3/Class2. So your edit is correct.
Basically, in terms of leveling, calculate the monster's level like this:
(challenge rating) + (class level) - (bonus levels)
The monster advances in level when either:
So in the Minotaur example above, the Minotaur is a Minotaur 4 / Barbarian 8. For experience totals, he's a tenth level character. He levels up when he acquires enough experience points to reach eleventh level. At that point he becomes a Minotaur 4 / Barbarian 9.
Current experience level: 4 + 8 - 2 = 10
Next experience level: 4 + 8 - 2 + 1 = 11