As pointed out by Snowball, the problem is inherently hard, see also this paper.
However, it can be done much faster in general than generating all the codewords.
I explain the idea for linear $[n,k]$ codes $C$ with $n = 2k$.
First, we construct two generator matrices $G_1 = (I\ A)$ and $G_2 = (B\ I)$ of $C$ where $I$ is the $(k\times k)$ unit matrix and $A,B$ are two $(k\times k)$ matrices. This is only possible if the positions $1,\ldots,k$ and $k+1,\ldots n$ form two information sets of $C$. If this is not the case, we have to find a suitable coordinate permutation first.
Now a codeword of weight $w$ has weight at most $\lfloor w/2\rfloor$ either in the first or in the second $n$ coordinates.
Thus, we can find all codewords of weight $\leq w$ among the codewords $x G_1 = (x, xA)$ and $x G_2 = (Bx, x)$, where $x$ is a vector of length $k$ and Hamming weight at most $\lfloor w/2\rfloor$.
So we can find the minimum distance $d$ of $C$ if we do this iteratively for all $w = 1,2,3,\ldots, d$.
In this way, you have to generate only a small fraction of all the codewords to find the minimum distance, and the idea can be generalized to any linear code. The first step then is to find a covering of the coordinates with information sets. However, the algorithm is still exponential, of course.
The webpage codetables.de is a valuable source for bounds on the best known minimum distances for fixed $q$, $n$ and $k$.
Let $c(x) = \sum_{i=0}^{N-1} c_i x^i$ denote the polynomial corresponding
to the codeword $\mathbf c = [c_0, c_1, \ldots, c_{N-1}]$ of a cyclic binary Hamming
code with generator polynomial $g(x)$. Note that $N = 2^m-1$ for some
positive integer $m$ and that $g(x)$ is a primitive
polynomial of degree $m$. Let $\alpha \in \mathbb F_{2^m}$ be a root of
$g(x)$ and note that $\alpha$ has order $2^m-1$.
The parity check matrix $H$ of this cyclic binary Hamming code can be viewed as
$[1, \alpha, \cdots, \alpha^{N-1}]$. If you are unfamiliar with this notion, then
express each $\alpha^i$ as a column vector to get the
usual binary representation. But, with this formulation,
$H\mathbf c^T = \mathbf0$ is equivalent to $c(\alpha) = 0$ which is
exactly what the polynomial formulation says in other terms: each
codeword polynomial is a multiple of $g(x)$ which happens to have
$\alpha$ as a root, and so $c(\alpha) = 0$.
Let $\mathbf c$ be transmitted and $\mathbf r = \mathbf c + \mathbf e$ denote
the received word. In terms of polynomials, $r(x) = \sum_i r_ix^i$
is the received word polynomial where $r_i = c_i + e_i$ with
$e(x)$ denoting the error word polynomial corresponding to the error
word $\mathbf e$. Note that $r(x) = c(x) + e(x)$. The receiver computes
$$H\mathbf r^T = H(\mathbf c + \mathbf e)^T =
H\mathbf c^T + H\mathbf e^T = \mathbf 0 + H\mathbf e^T = H\mathbf e^T.$$
In terms of polynomials, computing $H\mathbf r^T$ is the same as
evaluating $r(x)$ at $\alpha$, andso the above equation can be
expressed as
$$r(\alpha) = c(\alpha) + e(\alpha) = 0 + e(\alpha) = e(\alpha).$$
If a single error has occurred, then $\mathbf e$ has Hamming weight $1$,
and $e(x)$ is a monomial $x^i$ for some $i$, $0 \leq i \leq N-1$.
Thus, the bit in the $i$-th position has been received incorrectly.
In terms of polynomials, the syndrome is
$e(\alpha) = x^i\bigr |_{x=\alpha^i} = \alpha^i$. If two errors
have occurred, the syndrome is $\alpha^i + \alpha^{i^\prime} = \alpha^j$.
The decoder for the cyclic Hamming code cannot tell whether one
or two errors have occurred: if the symdrome equals $\alpha^\ell$,
it simply inverts $r_\ell$ to correct the error.
The extended Hamming code has an overall parity bit $c_N$
whose value is chosen to ensure that the extended codeword
$\hat{\mathbf c} = (\mathbf c, c_N)$ has even Hamming weight.
Suppose that an extended Hamming code is being used and
it is known that if there are two channel errors,
then they are adjacent errors not involving the overall
parity bit.
Let $\hat{\mathbf r} = (\mathbf r, r_N)$ be the received word for
the extended Hamming code. If $\hat{\mathbf r}$ has odd Hamming
weight, then the decoder assumes that a single error has
occurred, and if $r(\alpha) = \alpha^\ell$, the decoder inverts
$r_\ell$.
But if $\hat{\mathbf r}$ has even Hamming weight and
$r(\alpha) = \alpha^\ell \neq 0$, then the decoder assumes that
$e(x) = x^i + x^{i+1}$ (double adjacent error) and so
$r(\alpha) = e(\alpha) = \alpha^i + \alpha^{i+1} = \alpha^\ell.$
Since $\alpha^i = \alpha^\ell(1+\alpha)^{-1}$, the
decoder can find the value of $i$ and then invert $r_i$ and $r_{i+1}$.
In this way, single errors and double adjacent errors not involving
the overall parity bit can be corrected with an extended Hamming code.
Best Answer
Assume such a code $C$ exists. It has a generator matrix $G=(I|A)$, with a fixed 5x5 block $A$. By general results $C$ then has a parity check matrix $H=(A^T|I)$. Because $C$ is self-dual, $H$ also has to be generator matrix. Therefore $H$ and $G$ must be row-equivalent. Therefore we must have $H=A^TG$, so $A$ has to be invertible and its transpose must be equal to its inverse.
This means that the rows of $A$ are orthogonal to each other. But all the rows of $A$ must have an odd weight $\ge3$. If one of the rows of $A$ has weight five, then this is an immediate contradiction, because that row will not be orthogonal to the other rows. After all they then share an odd number of common 1s. So all the rows of $A$ must have weight $3$ exactly. Here there are at least two ways to proceed.
I) An easy induction then proves that the weights of all words of $C$ must be divisible by four. Thus $C$ is doubly even, and its length has to be a multiple of eight by the result cited by azimut contradicting the assumption.
II) We can also observe that any pair of rows of $A$ must have exactly two ones in common. There are undoubtedly many ways of seeing that there does not exist a set of five orthogonal vectors of length five and weight 3. For example, if some subset of three such vectors shares the same doublet of 1s, then there is no room for a fourth vector (easy to see). If no such subset exists, then we can find four such vectors, but there combined support has size four only, and it is impossible to find a fifth.
As pointed out in the comments, Gleason's theorem also forces the existence of a word of weight six leading to the contradiction described in the second paragraph. The point of including approach II was to avoid using Gleason's theory altogether.