Counting $k$-subsets of $N$ integers whose gcd is $1$ is equivalent to the problem of counting set covers:
Given a set $X$, and a family $\cal F$ of $N$ subsets of $X$, count the $k$-subsets of $\cal F$ whose union is $X$.
To see this, let $X$ be the set of primes dividing any of the $N$ integers, and then identify each integer with the set of primes in $X$ not dividing that integer. Then the gcd of a set of $k$ integers is $1$ iff the union of the corresponding $k$ sets is all of $X$.
Set cover problems are difficult in general. Finding the minimum size of a set cover is known to be NP-hard. van Rooij [vR] gives an exponential-time algorithm for counting set covers. In general, an efficient algorithm is exceedingly unlikely. So, especially if $k$ is fixed at $4$, simply trying all $k$-subsets is a reasonable algorithm.
[vR] Johan M. M. van Rooij, Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Number. In Algorithms and Complexity: 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010, Proceedings (Google eBook).