Tikz Node command not shifting its position correctly

You should use positioning for all the positioning.

\documentclass[tikz,border=3mm]{standalone}
\usetikzlibrary{arrows.meta,automata,positioning}
\begin{document}
   \begin{tikzpicture}[>=Stealth,shorten >=1pt,auto,node distance=1.6cm]
        \node[state] (S) {$S$};
        \node[state] (A) [above right=of S] {$A$};
        \node[state] (B) [above right=of A] {$B$};
        \node[state] (C) [below right=of A] {$C$};
        \node[state] (D) [above right=of C] {$D$};
        \node[state] (G) [below right=of D] {$G$};

        \path[->] (S) edge node {$1$} (A);
        \path[->] (A) edge node {$3$} (B);
        \path[->] (B) edge node {$3$} (D);
        \path[->] (D) edge node {$3$} (G);
        \path[<-] (G) edge [bend left] node {$12$} (S)
        edge node {$2$} (C);
        \path[<-] (C) edge node {$1$} (A);
        \path[->] (C) edge node {$1$} (D);

        \node[right=2.5cm of D,yshift=-1cm]
        {
            \begin{tabular}{|c|c|}
                \hline
                State ($n$) & $h\left(n\right)$\\
                \hline
                $S$ & 4\\
                \hline
                $A$ & 2\\
                \hline
                $B$ & 6\\
                \hline
                $C$ & 1\\
                \hline
                $D$ & 3\\
                \hline
                $G$ & 0\\
                \hline
            \end{tabular}
        };
  \end{tikzpicture}
\end{document}

I think one of the more legible ways of doing this is to shift the node coordinate with the xshift and yshift option.

\documentclass{article}

\usepackage{tikz}

\usetikzlibrary{arrows.meta}

\begin{document}
\begin{tikzpicture}[>=stealth,shorten >=1pt,auto,node distance=2.5cm]
    \node (S) {$S$};
    \node (A) [above right of=S]  {$A$};
    \node (B) [above right of=A, node distance = 2cm, xshift = 1cm] {$B$};
    \node (C) [below right of=A, node distance = 2cm, xshift = 1cm] {$C$};
    \node (D) [above right of=C, node distance = 2cm, xshift = 1cm] {$D$};
    \node (G) [below right of=D] {$G$};

    \path[->] (S) edge node {$1$} (A);
    \path[->] (A) edge node {$3$} (B);
    \path[->] (B) edge node {$3$} (D);
    \path[->] (D) edge node {$3$} (G);
    \path[<-] (G) edge [bend left] node {$12$} (S)
    edge node {$2$} (C);
    \path[<-] (C) edge node {$1$} (A);
    \path[->] (C) edge node {$1$} (D);

    \node at ([xshift=4.5cm, yshift=-1cm]D) 
    {
    \begin{tabular}{|c|c|} \hline
        State ($n$) & $h\left(n\right)$ \\ \hline
        $S$         & 4                 \\ \hline
        $A$         & 2                 \\ \hline
        $B$         & 6                 \\ \hline
        $C$         & 1                 \\ \hline
        $D$         & 3                 \\ \hline
        $G$         & 0                 \\ \hline
    \end{tabular}
    };
\end{tikzpicture}
\end{document}