Data structure for finding nearest squares from current square
Since you only measure distances from the centers of the squares, you can restate your problem as follows:
Maintain a dynamic collection $X$ of $n$ points in Euclidean space so that you can quickly find the $k$ nearest neighbors in $X \setminus \{p\}$ of a query point $p \in X$. 

Using the data structure described here you can maintain such a collection in $O(\log^3 n)$ expected amortized time per insertion and $O(\log^6 n)$ expected amortized time per deletion,  after a preproessing requiring $O(n \log^2 n)$ expected time.

The data structure supports nearest neighbor queries (given a point $q$, report the point in $X$ that is closest to $q$) in $O(\log^2 n)$ worst-case time. Then, you can report the $k$ nearest neighbors of $p \in X$ in $O(k \log^6 n)$ expected amortized time as follows:


Delete $p$ from $X$ in $O(\log^6 n)$ expected amortized time.
Repeat $k$ times:


Query the data structure for the nearest neighbor $p' \in X$ of $p$ in $O(\log^2 n)$ worst-case time.
Report $p'$ as one of the $k$ nearest neighbors of $p$.
Delete $p'$ from $X$ in $O(\log^6 n)$ expected amortized time.

Reinsert all deleted points in $X$ in $O(k \log^3 n)$ expected amortized time.