3. First, prove the existence of $k$. In fact, when $n$ is even, $\left((x+1)^{n}, x^{n}+1\right)=1$, so there exist rational coefficient polynomials $f^{*}(x), g^{*}(x)$, such that
$$1=f^{*}(x) \cdot(x+1)^{n}+g^{*}(x)\left(x^{n}+1\right) \text {. }$$

Let $k$ be a common multiple of the denominators of all the coefficients of $f^{*}(x)$ and $g^{*}(x)$, and set $f(x)=k f^{*}(x), g(x)=k g^{*}(x)$, then $f(x), g(x)$ are integer coefficient polynomials, and $k=f(x)(x+1)^{n}+g(x)\left(x^{n}+1\right)$.
Thus, the existence of $k$ is proven.
Next, find the minimum value of $k$, denoted as $k_{0}$. Let $n=2^{a} t$, where $t$ is odd, and $\alpha$ is a non-negative integer. Denote $m=2^{\alpha}$. Then, we have $x^{n}+1=\left(x^{m}\right)^{t}+1=\left(x^{m}+1\right) \cdot h(x)$, where $h(x)$ is an integer coefficient polynomial.
Let the $m$ roots of $x^{m}+1=0$ be $w_{j}=\mathrm{e}^{\mathrm{i} \cdot \frac{2 j-1}{m} \pi}, j=1,2, \cdots, m, m=2^{\alpha}$.
If a positive integer $k$, and integer coefficient polynomials $f(x), g(x)$ satisfy $k=f(x) \cdot(x+1)^{n}+g(x)\left(x^{n}+1\right)$, then $k=f\left(w_{j}\right)\left(w_{j}+1\right)^{n}, j=1,2, \cdots, m$, thus we have
$$k^{m}=\prod_{j=1}^{m} f\left(w_{j}\right) \cdot \prod_{j=1}^{m}\left(w_{j}+1\right)^{n} \text {. }$$

Let $\sigma_{1}=\omega_{1}+\omega_{2}+\cdots+\omega_{m}, \sigma_{2}=\omega_{1} \omega_{2}+\omega_{1} \omega_{3}+\cdots+\omega_{m-1} \omega_{m}$,
...
$$\sigma_{m}=\omega_{1} \omega_{2} \cdots \omega_{m} \text {. }$$

By Vieta's formulas, $\sigma_{j}$ are integers, $j=1,2, \cdots, m$. Since $\prod_{j=1}^{m} f\left(\omega_{j}\right)$ is an integer coefficient symmetric polynomial in $\omega_{1}, \omega_{2}, \cdots, \omega_{m}$, it can be expressed as an integer coefficient polynomial in $\sigma_{1}, \sigma_{2}, \cdots, \sigma_{m}$, thus it is an integer. Also, because
$$\begin{aligned} \prod_{j=1}^{m}\left(\omega_{j}+1\right)^{n} & =\left[\prod_{j=1}^{m}\left(\omega_{j}+1\right)\right]^{n} \\ & =\left(1+\sigma_{1}+\sigma_{2}+\cdots+\sigma_{m}\right)^{n}=2^{n}, \end{aligned}$$

we have $2^{n} \mid k^{m}$, thus $2^{\prime} \mid k, k \geqslant 2^{t}$.
On the other hand, we denote $E(x)=(x+1)\left(x^{3}+1\right) \cdots\left(x^{2 m-1}+1\right)=(x+1)^{m} \cdot F(x)$.
For a fixed $j \in\{1,2, \cdots, m\}$, consider the set $\left\{\omega_{j}, \omega_{j}^{3}, \omega_{j}^{5}, \cdots, \omega_{j}^{2 m-1}\right\}$, all elements of which are roots of $x^{m}+1=0$, and are distinct, hence it is the solution set of $x^{m}+1=0$. Thus
$$E\left(\omega_{j}\right)=\left(1+\omega_{j}\right)\left(1+\omega_{j}^{3}\right) \cdots\left(1+\omega_{j}^{2 m-1}\right)=\left(1+\omega_{1}\right)\left(1+\omega_{2}\right) \cdots\left(1+\omega_{m}\right)=2 \text {, }$$

i.e., $\omega_{j}$ is a root of $E(x)-2$. Therefore, we can set $G(x)\left(x^{m}+1\right)+2=E(x)=(x+1)^{m} F(x)$, raising both sides to the $t$-th power, we get $G^{*}(x) \cdot\left(x^{m}+1\right)+2^{t}=(x+1)^{n} F^{c}(x)$, where $G^{*}(x)$ is some integer coefficient polynomial.
Since $x^{n}+1=\left(x^{m}+1\right) h(x)$, where $h(x)$ satisfies $h(-1)=1$. Therefore, we can set
$$c(x) \cdot(x+1)=h(x)-1,$$

raising both sides to the $n$-th power, we get $C^{n}(x) \cdot(x+1)^{n}=h(x) \cdot d(x)+1$, where $d(x)$ is some integer coefficient polynomial.
From (1) and (2), we have $G^{*}(x) d(x) \cdot\left(x^{n}+1\right)=G^{*}(x) \cdot\left(x^{m}+1\right) \cdot d(x) \cdot h(x)=$
$$\left[(x+1)^{n} F^{2}(x)-2^{2}\right] \cdot\left[C^{n}(x)(x+1)^{n}-1\right]=(x+1)^{n} \cdot U(x)+2^{t},$$

where $U(x)$ is some integer coefficient polynomial.
Therefore, there exist integer coefficient polynomials $f(x), g(x)$, where $f(x)=-U(x), g(x)=G^{*}(x) \cdot d(x)$, such that $f(x) \cdot (x+1)^{n}+g(x) \cdot\left(x^{n}+1\right)=2^{t}$.
In conclusion, the minimum value of $k$ is $k_{0}=2^{t}$, where $n=2^{a} \cdot t, t$ is odd, and $\alpha$ is a non-negative integer.