Pointed Discussion

Its not going to be useful by turn two unless your playing . . . wait, are there any three drops that have a power of five? If not (or a scarce amount, I can't determine because the advanced gatherer dosn't seem to be working at the moment) then the only time this guy can be useful is if he's being played late game in an aggro deck.

Shoulda been can't attack unless a creature with power 4 or greater also attacks, might of used it then.

it costs too much. 2 for a 4/4? thats outragesours. toshiro is a better two drop

Okk turn two, Ball Lightning turn three?

Combos with cards that care about a creature's power or toughness, as well as cards that get creatures with low CMC out of the graveyard.

I have a sardonic urge to combo Okk with Soul Foundry and fill the entire battlefield with Okks. Now if only I could find a way to make them able to attack without casting any other creatures...

Lets see here... Ruinous Minotaur, Woolly Thoctar, Mijae Djinn, Lavacore Elemental, Cosmic Larva, and Avatar of Discord. Those are just the red ones that stick around after turn 1. I outta make a mono red out of cards that make this guy work.

@WhiteyMcFly: I can definitely see this being playable alongside Ruinous Minotaur and perhaps Cosmic Larva.

Maybe you could also include Kiln Fiend, Brute Force (pretty sick on a Kiln Fiend btw) and some Ma.ss Hysteria to get the most out of your creatures. Oh yeah, and don't forget the burn spells.

Phyrexian Dreadnought. A 12/12 for 7.

Cliffrunner Behemoth also seems like a decent choice with him.
Or some really bad guys like Abyssal Persecutor, Juzám Djinn or Grinning Demon. Green and black are besides red likely the best colors to find cheap "fight compagnons" to make this guy move a leg. Try a Phyrexian Negator xD
If he wasn't equally hard to cast in a non-monoblack deck, i'd think about using Phylactery Lich. Avatar of Discord on the other hand shouldn't be a problem in a red/black deck.

Strenchskipper, Boggart Mob and Goblin Goon would work in a goblin deck. (But in the case of the latter, you'd have to provide enough creatures to look for the goon again.)
There are even several one-drops that can help: Death's Shadow, Scute Mob and Dragonmaster Outcast.
Volcano Hellion would also synergize with the shadow.
Hunted Horror is also nice, since Okk can destroy one of the 3/3 centaur tokens, and disregarding other creatures your opponent will have to take seven damage from it if he wants to kill Okk with both centaurs.
If your opponent has creatures, Sheltering Ancient is pretty neat.
Tempting Wurm...still doesn't sound too tempting :D

Rumbling Slum or Spellbreaker Behemoth is certainly a good choice for green/red.
Balduvian Horde and Emperor Crocodile are two classics (aside from Juzám of course).
Gathan Raiders is a nice or even better alternate for Balduvian Horde.
(If you like coin flipping: Goblin Mutant, Fickle Efreet and Mijae Djinn are for you.)

Enchantments that cause cip-triggers based on the creature's power also synergize with him:
Pandemonium, Electropotence, Warstorm Surge can cause damage, and Kavu Lair lets you draw a card.

Nulltread Gargantuan is also blue, but too interesting not to mention.
Add Shivan Wumpus or Argothian Wurm and let them live happily together in the Kavu Lair.

Last but not least, good old Rancor can also help your smaller creatures to get stronger than Okk.

It just bugs me a little that Okks abilities are variable, and not specified to say "power 5 or greater", because in that case you could have two Okks fighting together with a little power boost.

Stenchskipper

Hmmm Orcish Con***s.

Really? Con s c r i p t s is somehow a diabolical word??

I can see some applications for this. Running it in a deck with high-power quick beaters like Arc Runner, Ball Lightning, Cosmic Larva, Lavacore Elemental, Blistering Firecat, Zektar Shrine Expedition and Juggernaut, plus support for them, like Fling. Throw in Kiki-Jiki, Mirror Breaker because it fits well, and some burn to finish your opponent off or remove blockers...

It might not seem worth it, but really, red tends to get pretty weak two-drops considering how fast it needs to be.

Fun build around, similar to Veteran Brawlers. 4/4s for 2 are incredibly hard to deal with because of the pressure they put on you both to have a big attacker to get through them, and to have a big enough blocker or removal for them; but it sucks to have to remove a 2-drop with premium removal.

Turn 1: Jackal Familiar
Turn 2: Okk
Turn 3: Any of these:

Ball Lightning (Swing for 11)
Arc Runner (Swing for 10)

You can also use Cosmic Larva which will stick around...but I'd suggest using something like Lightning Greaves to give it haste when it enters the battlefield.