Is this a caching problem ? - and how to solve ?

I have updated a Joomla site to Joomla 2.5.17 and the nice gk_news with K2.
The site has some 2368 items/articles. To speed the user-load in the browser I have installed the Lazy Load.
Everything is working fine and I think the load speed for users are fine

My problem is when I change position of a module from - lets say - Sidebar to Inset or ordering - the update in the UI takes hours, and some updates will not get through.
And - when creating a new item/article it can takes hours too - before it shows up in the UI.

I have activated gavickExtCache, plg_gkcache and Cache - ordering '0'

Is this a caching problem ? - and how to solve ?

I think you are trying to optimize wrong area. With this amount of articles the problems is probably in database not in template or front-end. Please ask you hosting provider whether the database may be optimized or just remove old items to decrease database size and speed up all queries.