I'll address the last question about an a priori bound for $\epsilon$. I assume that the elements of $A$ are nonnegative, otherwise the problem does not seem to make sense (except that $\epsilon=1$ is always an answer).

Proof. The columns of $A$ form a set $S$ of cardinality $n$ in $\mathbb R^m$. For a given $\epsilon$, a suitable $B$ exists if and only if there exists a subset $T\subset S$ of cardinality at most $m$ such that the convex hull $conv(T)$ majorizes the set $(1-\epsilon)S$ in the following sense: for every $v\in S$, there is a point in $conv(T)$ which is component-wise greater than $(1-\epsilon)v$. And this majorization is implied by the following: $conv(sym(T))$ contains the set $(1-\epsilon)S$, or equivalently, the set $(1-\epsilon)conv(sym(S))$, where by $sym(X)$ denotes the minimal origin-symmetric set containing $X$, that is, $sym(X)=X\cup -X$.

On the other hand, if $S$ is contained in the unit sphere and separated away from the coordinate hyperplanes, you must choose $T$ to be a $\sqrt\epsilon$-net in $S$. This gives the lower bound; the "worst case" is a uniformly packed set of $n=C(m)\cdot k$ points on the sphere.

I'll address the last question (about an a priori bound for $\epsilon$).

Proof. The columns of $A$ form a set $S$ of cardinality at most $n$ in $\mathbb R^m$. For a given $\epsilon$, a suitable $B$ exists if and only if there is a subset $T\subset S$ of cardinality at most $m$ such that the convex hull $conv(T)$ majorizes the set $(1-\epsilon)S$ in the following sense: for every $v\in S$, there is a point in $conv(T)$ which is component-wise greater than $(1-\epsilon)v$. And this majorization is implied by the following: $conv(sym(T))$ contains the set $(1-\epsilon)S$, or equivalently, the set $(1-\epsilon)conv(sym(S))$, where by $sym(X)$ denotes the minimal origin-symmetric set containing $X$, that is, $sym(X)=X\cup -X$.

On the other hand, if $S$ is contained in the unit sphere and separated away from the coordinate hyperplanes, you must choose $T$ to be a $\sqrt\epsilon$-net in $S$. This gives the lower bound; the "worst case" is a uniformly packed set of $n=C(m)\cdot k$ points on the sphere.

UPDATE.

Fritz John theorem, also known as John Ellipsoid Theorem, says that for any origin-symmetric convex body $K\subset\mathbb R^m$, there is an ellipsoid $E$ (also centered at the origin) such that $E\subset K\subset\sqrt m E$. (There is a non-symmetric variant as well but the constant is worse.) The linear transformation that I used just sends $E$ to the unit ball. There are lecture notes about John ellipsoid here and probably in many other sources.

Comparing scaling distance (see also Banach-Mazur distance) and Hausdorff distance between convex bodies is based on the following. The scaling distance is determined by the worst ratio of the support functions of the two bodies, and the Hausdorff distance is the maximum difference between the support functions. Once you captured the bodies between two balls, you can compare relative and absolute difference. This should be explained in any reasonable textbook in convex geometry; unfortunately I'm not an expert in textbooks, especially English-language ones.

By "packing argument" I mean variants of the following argument showing that for any $\epsilon$, any subset $S$ of the unit ball in $\mathbb R^m$ contains an $\epsilon$-net of cardinality at most $(1+2/\epsilon)^m$. Take a maximal $\epsilon$-separated subset $T$ of $S$, it is always an $\epsilon$-net. Since $T$ is $\epsilon$-separated, the balls of radius $\epsilon/2$ centered at the points of $T$ are disjoint, hence the sum of their volumes is no greater than the volume of the $(1+\epsilon/2)$-ball that contains them all. Writing the volume of an $r$-ball as $c(m)\cdot r^m$ yields the result. This argument gives a rough estimate $$ \epsilon \le (2\sqrt m+1) k^{-1/m} $$ in the original problem (up to errors in my quick computations). To improve the exponent one can consider the $(m-1)$-dimensional surface of $P$ rather that the whole ball.