Let $A$ be an $n \times n$-matrix, and let $1 \leq k \leq n$. Which algorithms do exist, or what is know about the complexity of computing determinants of all $k \times k$-minors?The naive algorithm has complexity $\Theta( {n \choose k}^2 k! )$. If we apply Gaussian elemination for each minor $\Theta( {n \choose k}^2 k^3 )$. Of course, there is a dynamic programming approach, too, but I am not firm enough to compute its complexity.I am also interested whether there is a lower bound actually known. 
Complexity of determinant of k-minors
ds.algorithms
There are clasical algorithms [1], [2], [3] to compute the determinant of a $k\times k$  matrix using $O(k^\omega)$ floating-point operations, where $O(k^\omega)$ is the number of operations that you need for matrix multiplication.  Therefore, you can get a better bound $$\textstyle O(\binom{n}{k}^2 k^\omega )$$, which is the cost of computing all of them individually and listing. You can let $\omega=2.3727$. For implementations the Strassen algorithm is often used with has $\omega=2.807$.In particular, the third reference uses the Strassen algorithm, but explicitly mentions:In Section 5 we show that matrix multiplication, triangular factorization, and  inversion are equivalent in computational complexity.