Sub and super scripts touching lines in table

You can add some vertical padding to the cells, either with cellspace, which defines a minimal white space at the top and bottom of cells in columns with specifier prefixed with the letter S, or with makecell, which adds a fixed vertical spacing at the top and bottom of all cells, with the \makegapedcells command.

Note you do not have to set the columns in paragraph mode: the second code sets column widths to their natural widths.

    \documentclass{article}
    \usepackage{amsmath, array, makecell}
\usepackage{cellspace} %
\setlength\cellspacetoplimit{4pt}
\setlength\cellspacebottomlimit{4pt}


\begin{document}

\begin{table}[htbp]
\centering
    \begin{tabular}{| S{m{2.7cm}} | Sl|}%{m{8cm}}
        \hline
        \textbf{Marginalised term} & \textbf{3 variable terms} \\
        \hline \hline
        $H_\partial^{12}(\{12\})$ &
        $\begin{aligned}
            &H_\partial^{123}(\{12\}) + H_\partial^{123}(\{3\}\{12\}) \\
            &+ H_\partial^{123}(\{12\}\{13\}) + H_\partial^{123}(\{12\}\{23\}) \\
            &+ H_\partial^{123}(\{12\}\{13\}\{23\})
            \end{aligned}$ \\
        \hline
        $H_\partial^{12}(\{1\})$ &
        $H_\partial^{123}(\{1\})+H_\partial^{123}(\{1\}\{23\})+H_\partial^{123}(\{1\}\{3\})$ \\
        \hline
        $H_\partial^{12}(\{2\})$ &
        $H_\partial^{123}(\{2\})+H_\partial^{123}(\{2\}\{13\})+H_\partial^{123}(\{2\}\{3\})$ \\
        \hline
        $H_\partial^{12}(\{1\}\{2\})$ &
        $H_\partial^{123}(\{1\}\{2\})+H_\partial^{123}(\{1\}\{2\}\{3\})$ \\
        \hline
  \end{tabular}
\end{table}

\begin{table}[htbp]
\centering\setcellgapes{4pt}\makegapedcells \renewcommand\theadfont{\normalsize\bfseries}%
%
 \begin{tabular}{|l| l|}%{m{8cm}}
 \hline
 \thead{Marginalised\\ term} & \thead{3 variable terms} \\
 \hline \hline
 $H_\partial^{12}(\{12\})$ &
 $\begin{aligned}
 &H_\partial^{123}(\{12\}) + H_\partial^{123}(\{3\}\{12\}) \\
 &+ H_\partial^{123}(\{12\}\{13\}) + H_\partial^{123}(\{12\}\{23\}) \\
 &+ H_\partial^{123}(\{12\}\{13\}\{23\})
 \end{aligned}$ \\
 \hline
 $H_\partial^{12}(\{1\})$ &
 $H_\partial^{123}(\{1\})+H_\partial^{123}(\{1\}\{23\})+H_\partial^{123}(\{1\}\{3\})$ \\
 \hline
 $H_\partial^{12}(\{2\})$ &
 $H_\partial^{123}(\{2\})+H_\partial^{123}(\{2\}\{13\})+H_\partial^{123}(\{2\}\{3\})$ \\
 \hline
 $H_\partial^{12}(\{1\}\{2\})$ &
 $H_\partial^{123}(\{1\}\{2\})+H_\partial^{123}(\{1\}\{2\}\{3\})$ \\
 \hline
 \end{tabular}
\end{table}

    \end{document} 

There is probably a better way, but here I use a combination of struts. I added \upstrut to the top of the aligned stack, \downstrut to the bottom of the aligned stack, and \mystrut to the simple lines.

\documentclass{article}
\usepackage{tabularx,amsmath}
\newcommand\upstrut{\rule{0pt}{12pt}}
\newcommand\downstrut{\rule[-6pt]{0pt}{6pt}}
\newcommand\mystrut{\upstrut\downstrut}
\begin{document}
\begin{table}[htbp]
\begin{center}
    \begin{tabular}{| m{2.7cm} | m{8cm}|}
        \hline
        \textbf{Marginalised term} & \textbf{3 variable terms} \\
        \hline \hline 
        $H_\partial^{12}(\{12\})$ & 
        $\begin{aligned} 
            &\upstrut H_\partial^{123}(\{12\}) + H_\partial^{123}(\{3\}\{12\}) \\
            &+ H_\partial^{123}(\{12\}\{13\}) + H_\partial^{123}(\{12\}\{23\}) \\ 
            &+ H_\partial^{123}(\{12\}\{13\}\{23\}) \downstrut 
            \end{aligned}$ \\
        \hline
        $\mystrut H_\partial^{12}(\{1\})$ &  
        $H_\partial^{123}(\{1\})+H_\partial^{123}(\{1\}\{23\})+H_\partial^{123}(\{1\}\{3\})$ \\
        \hline
        $\mystrut H_\partial^{12}(\{2\})$ &  
        $H_\partial^{123}(\{2\})+H_\partial^{123}(\{2\}\{13\})+H_\partial^{123}(\{2\}\{3\})$ \\
        \hline
        $\mystrut H_\partial^{12}(\{1\}\{2\})$ &  
        $H_\partial^{123}(\{1\}\{2\})+H_\partial^{123}(\{1\}\{2\}\{3\})$ \\
        \hline
  \end{tabular}
\end{center}
\end{table}
\end{document}

Alternatively, one could add a \stackgap to a term in each row, which ads a (default) 3pt buffer above and below the term. An optional argument can change the stack gap value:

\documentclass{article}
\usepackage{tabularx,amsmath,stackengine}
\begin{document}
\begin{table}[htbp]
\begin{center}
    \begin{tabular}{| m{2.7cm} | m{8cm}|}
        \hline
        \textbf{Marginalised term} & \textbf{3 variable terms} \\
        \hline \hline 
        $H_\partial^{12}(\{12\})$ & 
        \addstackgap{$\begin{aligned} 
            &H_\partial^{123}(\{12\}) + H_\partial^{123}(\{3\}\{12\}) \\
            &+ H_\partial^{123}(\{12\}\{13\}) + H_\partial^{123}(\{12\}\{23\}) \\ 
            &+ H_\partial^{123}(\{12\}\{13\}\{23\}) 
            \end{aligned}$} \\
        \hline
        \addstackgap{$H_\partial^{12}(\{1\})$} &  
        $H_\partial^{123}(\{1\})+H_\partial^{123}(\{1\}\{23\})+H_\partial^{123}(\{1\}\{3\})$ \\
        \hline
        \addstackgap{$H_\partial^{12}(\{2\})$} &  
        $H_\partial^{123}(\{2\})+H_\partial^{123}(\{2\}\{13\})+H_\partial^{123}(\{2\}\{3\})$ \\
        \hline
        \addstackgap{$H_\partial^{12}(\{1\}\{2\})$} &  
        $H_\partial^{123}(\{1\}\{2\})+H_\partial^{123}(\{1\}\{2\}\{3\})$ \\
        \hline
  \end{tabular}
\end{center}
\end{table}
\end{document}

The most appealing way to typeset this table is without any vertical lines and far fewer, but well-spaced, horizontal lines. That way, the issue of subscript and superscript terms touching the horizontal lines never arises to begin with. And, no need to monkey around with \arraystretch.

Since almost all of the table's material is math-y stuff, I suggest usin an array environment instead of a tabular environment. If nothing else, you can save yourself having to type a lot of $ symbols.

Separately, since H_\partial occurs about 17 times in the table, I suggest you replace all instances with \Hp, where \Hp is defined in the preamble as, you guessed it, H_\partial.

\documentclass{article}
\usepackage{amsmath,booktabs,array}
\newcommand{\Hp}{H_\partial} % shortcut macro
\begin{document}
\begin{table}[htbp]
\centering

$\begin{array}{@{}ll@{}}
    \toprule
    \multicolumn{1}{@{}m{2.7cm}}{\textbf{Marginalised term}} & 
    \textbf{3 variable terms} \\
    \midrule
    \Hp^{12}(\{12\}) & 
    \!\begin{aligned}[t]
      &\Hp^{123}(\{12\}) + \Hp^{123}(\{3\}\{12\}) \\
      &\quad+ \Hp^{123}(\{12\}\{13\}) + \Hp^{123}(\{12\}\{23\}) \\ 
      &\quad+ \Hp^{123}(\{12\}\{13\}\{23\})  
    \end{aligned} \\
    \addlinespace
    \Hp^{12}(\{1\}) &  
    \Hp^{123}(\{1\})+\Hp^{123}(\{1\}\{23\})+\Hp^{123}(\{1\}\{3\}) \\
    \addlinespace
    \Hp^{12}(\{2\}) &  
    \Hp^{123}(\{2\})+\Hp^{123}(\{2\}\{13\})+\Hp^{123}(\{2\}\{3\}) \\
    \addlinespace
    \Hp^{12}(\{1\}\{2\}) &  
    \Hp^{123}(\{1\}\{2\})+\Hp^{123}(\{1\}\{2\}\{3\}) \\
    \bottomrule
\end{array}$

\end{table}
\end{document}