1) put AA right before # to the left. This is 00 written base 26.
2) go right until you encounter -. Put + there and then go left until you hit #. Increase that number (it will become AB). Then go right again.
3) if you encounter # while walking right, go left and compute coordinate of last - mathematically using cells to the left as memory with base-26 2-digit arithmetics. For arbitrary k and n it will be more than 2 of course, that's why it's O(log(k)+log(n)), but not a constant.
4) like in case of 2 run right/left by putting - instead of + until result becomes zero (decrease it with every - set).
5) Find rightmost - and paint everything to the left with +
6) Find - and stop there
Though, I heard in this forum that the checker is wrong as it stops when there are n-1 pluses, but not when invalid state/character pair is met. So, actually you will have to use O(n) states to calculate 'n' and then bring back this value to calculation area inside read/write head :)
I also came up with 604 lines solution. Just go to the right incrementing the state (200 instructions), then output "X # something_related_to_josephus # <" for X in range [2, 201]. You've spent 400 states. Now your state number should have the information how many steps left you should make outputting '+' -- you will need 199 instructions for this. After that you'll have to add 5 more instructions