For the arcs below the scheme, you need negative in
and out
angles. However, this answer is also to propose an arguably simpler way to draw the scheme as a matrix. The third example has the baselines aligned.
\documentclass[tikz,border=3mm]{standalone}
\usetikzlibrary{chains,%<- for the first picture
matrix}%<- for the second picture
\begin{document}
\begin{tikzpicture}[
start chain = going right,
node distance = 0pt,
MyStyle/.style={draw, minimum width=1.6em, minimum height=2em, outer sep=0pt, on chain}, ]
\node [MyStyle] (1) {$A$};
\node [MyStyle] (2) {$B$};
\node [MyStyle] (3) {$C$};
\node [MyStyle] (4) {$D$};
\node [MyStyle] (5) {$E$};
\node [MyStyle] (6) {$F$};
\node [MyStyle] (7) {$G$};
\node [MyStyle] (8) {$Q$};
\node [MyStyle] (9) {$B$};
\node [MyStyle] (10) {$G$};
\node [MyStyle] (11) {$A$};
\node [MyStyle] (12) {$D$};
\node [MyStyle] (13) {$W$};
\node [MyStyle] (14) {$B$};
\node [MyStyle] (15) {$n$};
\node [MyStyle] (16) {$6$};
\begin{scope}%[-{Stealth[length = 2.5pt]}]
%\draw (1.north) [out=25, in=155] to (2.north);
%\draw (1.north) [out=30, in=155] to (3.north);
\draw (1.north) [out=35, in=155] to (4.north);
\draw (1.north) [out=40, in=155] to (6.north);
\draw (1.south) [out=-40, in=-155] to (6.south);
\end{scope}
%\draw[decorate,decoration={brace, amplitude=10pt, raise=5pt, mirror}]
%(2.south west) to node[black,midway,below= 15pt] {$k$-elements} (7.south east);%
\end{tikzpicture}
\begin{tikzpicture}
\matrix[matrix of math nodes,column sep=-\pgflinewidth/2,
cells={nodes={draw, minimum width=1.6em, minimum height=2em,anchor=center,
alias=\the\pgfmatrixcurrentcolumn}}]
(mat){
A & B & C & D & E & F & G & Q & B & G & A & D & W & B & n & 6 \\ };
\draw (1.north) [out=35, in=155] to (4.north);
\draw (1.north) [out=40, in=155] to (6.north);
\draw (1.south) [out=-40, in=-155] to (6.south);
\end{tikzpicture}
\begin{tikzpicture}
\matrix[matrix of math nodes,column sep=-\pgflinewidth/2,
cells={nodes={draw, minimum width=1.6em, text height=1.2em,text depth=0.3em,anchor=center,
alias=\the\pgfmatrixcurrentcolumn}}]
(mat){
A & B & C & D & E & F & G & Q & B & G & A & D & W & B & n & 6 \\ };
\draw (1.north) [out=35, in=155] to (4.north);
\draw (1.north) [out=40, in=155] to (6.north);
\draw (1.south) [out=-40, in=-155] to (6.south);
\end{tikzpicture}
\end{document}

You may also want to make the arrows distinguishable. One option is to shift the point where the arrow attaches depending on the horizontal distance between start and target. This can be achieved with the show path construction
decoration.
\documentclass[tikz,border=3mm]{standalone}
\usetikzlibrary{matrix,arrows.meta,bending,calc,decorations.pathreplacing}%
\begin{document}
\tikzset{distinguishable arrows/.style={%
decoration={show path construction,
curveto code={
\draw[#1] let \p1=($(\tikzinputsegmentlast)-(\tikzinputsegmentfirst)$) in
([xshift=-\x1/40]\tikzinputsegmentfirst) .. controls
(\tikzinputsegmentsupporta) and (\tikzinputsegmentsupportb)
..([xshift=\x1/40]\tikzinputsegmentlast);
},
}}}
\begin{tikzpicture}[connect/.style=]
\matrix[matrix of math nodes,column sep=-\pgflinewidth/2,
cells={nodes={draw, minimum width=1.6em,
text height={height("A")+0.3em},text depth=0.3em,anchor=center,
alias=\the\pgfmatrixcurrentcolumn}}]
(mat){
A & B & C & D & E & F & G & Q & B & G & A & D & W & B & n & 6 \\ };
\begin{scope}[distinguishable arrows={-{Stealth[bend]}}]
\draw[decorate] (1.north) to[out=40, in=140] (2.north);
\draw[decorate] (1.north) to[out=50, in=130] (3.north);
\draw[decorate] (1.north) to[out=60, in=120] (4.north);
\draw[decorate] (1.north) to[out=70, in=110] (6.north);
\draw[decorate] (1.south) to[out=-70, in=-110] (6.south);
\end{scope}
\end{tikzpicture}
\end{document}

One can also implement other prescriptions.
in
andout
angles negative in the arc that is under the diagram:\draw (1.south) [out=-40, in=-155, below] to (6.south);
.