Hi!
I have joomla 2.5.14 and K2 v2.6.7 installed, and sometimes, in same browsers I 've got the message ' Forbidden Access (flooding)'
I do not have installed the sh404sef component at all.
Is there any " flood protection" settings for the K2 that causes this problem?

This is exactly the same problem that I am having. Can you check and see if you are shown in your Users menu as logged in or logged out. On my site the K2 users menu shows me as logged out, when actually I am signed into the site.

This error message is not coming from K2 or Joomla! so probably a third-party extension is causing this. Enable Joomla! debugging to see which file is raising this error.