Let f(X,k,m,r,n) be the function that takes as input a set X of k
positive integers X with maximum m, a positive integer r, and a
positive integer n which is smaller than two to the power r. Suppose f
returns the cardinality of the set of integers between 1 and n
inclusive that are divisible by at least one element in X.

Is there an algorithm that computes f in time polynomial in k, m, and
r ?

I am seeking either a proof that such an algorithm exists, or a proof
that no such algorithm exists, or a proof that the existence of such
an algorithm is equivalent to a published conjecture in the field.

Just so you know someone has looked at the problem.  I haven't
researched it yet, just pondered my own solutions. (Now I've done a
little searching)

It sounds like you have some variant of the Prime Counting Function. 
You probably already knew that judging from your question.
http://mathworld.wolfram.com/PrimeCountingFunction.html

Non-answers:
One method is roughly O(2^k * (Log2(m)^2)), which I just found out is
Mapes' Method.  You need to replace the product of the primes with the
LCM.  Instead of computing all the LCMs, you might change the problem
by making them all relatively prime and add some correction term. 
This method could be reduced to be polynomial in k if you had a
minimun for the set X that was large (some root of n).  Many of the
terms (with many betas) would be zero.
http://mathworld.wolfram.com/MapesMethod.html

Another method is about O(f(X,k,m,r,n) * Log2(k)).  You maintain a
heap of the multiples of X; basicly, it's an interative sieve.
http://mathworld.wolfram.com/Heap.html

I can describe them in more detail, but they don't satisfy your
constraints.

Good luck.

Perhaps this PhD thesis would have some answers.
Analytic computation of the prime-counting function.
http://www.cecm.sfu.ca/~wfgalway/
http://citeseer.nj.nec.com/context/1316286/0

This author has several papers relating to prime sieves.
http://euclid.butler.edu/~sorenson/research/papers.shtml

A preprint describing the algorithm used to compute pi(x) in the pi(x)
project.

http://numbers.computation.free.fr/Constants/Primes/Pix/piNalgorithm.ps
http://numbers.computation.free.fr/Constants/Primes/Pix/pixproject.html

Some general discussion on programming pi(x).  Someone commented about
how fast Mathematica's pi(x) function was.
http://mathforum.org/epigone/sci.math/dahsmofri/bl9hfugelt76ibp29m4bd57u00qrqmjb28@4ax.com