You can do a simple Breadth First Search from the start node. It starts with the first node, and adds all its neighbours to a queue. Then, it de-queues each node, finds its unvisited neighbors to the queue and marks the current node visited. The key observation here is that the all the vertices that are at some distance $d$ from the start vertex, are in one contiguous block in the FIFO queue. If you can keep track of how deep you are in the queue, you can stop after $k$-levels. More specifically, the moment you de-queue a vertex that you know is at a distance of $k$ from the start node, you don't have to enqueue any more, just go on till the queue is empty, and you are done. Using BFS in this way will give you vertices in increasing order of hops/distance from the start.
You can also adapt the Depth First Search algorithm for this, by limiting the depth to $k$. This is easier to code, but won't give vertices in order of distances from the start. So, for some of the discovered vertices, you may later find a shorter path. But no vertex will have to be discarded after being discovered in either methods.
Both these algorithms are linear in the size of the graph - $O(|V|+ |E|)$ even if they traverse the whole graph. But since you are stopping much sooner, they would be very efficient. More specifically, they will visit only those edges and vertices that are actually in the $k$-hop neighborhood, and nothing more -- $O(|V_s|+|E_s|)$, where $V_s$ and $E_s$ are the number of vertices and edges in the $k$-neighborhood subgraph. Another consideration can be that if $k$ is small but vertex degrees are very large, you might prefer DFS.
k-hops for all vertices:
If the graph is sparse, that is, $|E| = O(|V|)$, then running a BFS/DFS from each node should be the best option asymptotically. Rectangular or hexagonal lattice graphs are sparse graphs. So, complexity would be $O(|V|^2)$. I do not think that there should be anything asymptotically faster than this for sparse graphs, though there may be other solutions that are more efficient (but still quadratic).
If the graph is not sparse, you can compute the $k$-th power of the adjacency matrix in $O(n^{\omega}\log k)$ time, where $\omega$ is the constant of matrix multiplication. The current best known algorithm has $\omega = 2.3727$. But in practice, the simple cubic matrix multiplication ($\omega = 3$) is the most efficient. You could also use the all-pair shortest path algorithm by Floyd-Warshall and find those vertices that have distance atmost $k$. This is $O(|V|^3)$
If we remove one of the additional vertices from $G'$, the resulting graph contains an Eulerian walk $W_1$ since there are now two vertices of odd degree. Removing the next additional vertex splits $W_1$ into two walks, let's call them $W_1, W_2$. Removing the next vertex splits one of the walks $W_1, W_2$ into two walks again resulting in walks $W_1, W_2, W_3$. Repeat until all additional vertices have been removed, count the walks produced.
Since an Eulerian walk visits every edge exactly once, splitting it into several parts results in edge disjoint walks and because we only removed the additional edges and vertices, the resulting walks cover $G$.
Best Answer
If you are going to check edge existence only few times, why care about the time complexity? If you are going to check it regularly, why don't use some better data structure (adjacency matrix, as already mentioned).
But even with an incidence matrix, you can probably do better then O(E) and still call it an incidence matrix :).
Given an incidence matrix with row for each vertex and column for each edge, most of the elements of the matrix will be zeroes (there will be at most V nonzero elements on each row). That's called sparse matrix and it can be stored in the memory in some space efficient way, which also allows "skipping" long sequences of zeroes in constant time.
For example with simple list of lists representation, you have a list of pairs (columnindex, value) ordered by columnindex for each row, one pair for each nonzero element. In our case, just check rows u and v, whether they have an item with same columnindex. As they are both ordered and both have less then V items, it can be done in O(V).
Of course, it's a trade-off. Some other operations are less efficient if matrix is stored this way.