@1) As far as I am aware, the runtime of Lenstra's algorithm depends on the problem you are trying to solve:
For example, for the "Cutting Stock Problem" (CSP) the dimension-reduction-step can exploit the special structure of CSP and thereby yields a run time inferior to the naive/generic implementation.
@2) Lenstra's algorithm may be used to compute an $(OPT + 1)$-solution to the CSP, see "An $OPT + 1$ algorithm for the cutting stock problem with a constant number of object lengths" by K. Jansen and R. Solis-Oba.
As CSP is only a more compact way of formulating the "Bin Packing Problem", the algorithm can be used to find a nearly-optimal packing of objects into bins of a certain capacity.
The number of different object types is thereby the dimension $d$ of the problem (for example a postal service only allows packets of $d$ diffenent heights) and is responsible for the exponential term of the run time.
The actual number of objects only influences the run time polynomially.