The solution fills the rectangle in a spiral fashion, starting on the outside of the rectangle. It can be devided into two phases, where the second phase is repeated until the rectangle is completely filled:

After each phase, the Karas wait on each other using the barrier state "in corner".

During the first phase, when looking for an empty corner, a Kara may find another Kara in front. He then has to walk around the other one.

The second phase is repeated until the Karas have reached the middle of the rectangle. This is the case when there is cloverleaf or another Kara in front.

Note:
The solution does not work for the special case of a 2x2 square!