I claim that there can be no Borel $\mathbb{N}$-coloring of this graph. 

To see this, suppose toward contradiction that there is such a Borel coloring. 
Consider the forcing to add a generic Cohen real, in the form of a
function $g:\mathbb{N}\to\mathbb{N}$. So the forcing conditions
are finite partial functions from $\mathbb{N}\to\mathbb{N}$,
ordered by extension. Since the coloring has a Borel code, we may
interpret this code in the forcing extension $V[g]$ (where I use $V$ here as usual to denote the original set-theoretic universe, rather than your use to denote the underlying set of the graph $\mathbb{N}^{\mathbb{N}}$). Furthermore,
the interpretation of that coloring is still a coloring of the
corresponding graph as defined in the forcing extension $V[g]$,
since the assertion that a given Borel code codes a coloring for
that graph is a $\Pi^1_1$ assertion and hence absolute between the
universe $V$ and the forcing extension $V[g]$. So the generic
function $g$ gets some color, say $k$. This fact must be forced by
some finite piece of the generic function $p=g\upharpoonright n$.
That is, condition $p$ forces that the generic function gets color
$k$. But now let us modify $g$ to form a new function $g'$ by
making a single change beyond $p$. So $g'$ is also generic, and
furthermore extends $p$, and the corresponding forcing extensions
are the same $V[g]=V[g']$. It follows that $g'$ must also get
color $k$, since this was forced by $p$, and this contradicts the
fact that $g$ and $g'$ are adjacent in the graph. So there can be
no such coloring.  **QED**

This argument is similar to an argument showing that almost-equality has no Borel selector, and a similar idea appears in [this MO question}(http://mathoverflow.net/a/47191/1946) concerning the non-existence of a Borel diagonalization against countable sets of reals.