### Part 1:
We need to find the smallest integer $k$ such that if the minimum number in $A, B \in S$ are both $\geq k$, then $A \rightarrow B$ implies $B \rightarrow A$.

We claim that the smallest integer $k$ is $8$.

Proof:

1. **$k \leq 7$ does not satisfy the condition:**

Consider the counterexample $A = (1956, 7, 7, 7, 7, 7, 7, 7, 7, 7)$ and $B = (1938, 9, 9, 9, 9, 9, 9, 9, 9, 9)$. It is clear that $A \rightarrow B$. However, $B \not\rightarrow A$ because each of the entries from the 2nd to the 10th in $B$ must be subtracted by 9 at least once. After the last subtraction, the remaining entries should be greater than or equal to 8, which contradicts the condition.

2. **$k = 8$ does satisfy the condition:**

Denote the numbers in the $i$-th entry as $x_i$. For any $i$ and $j$, $x_i - x_j \mod 10$ is conserved. Assume $8 \leq a_1 \leq a_2 \leq \cdots \leq a_{10}$ for $A$. We need to show that for each $i$, we can operate on $B$ so that $x_1 - a_1 = x_2 - a_2 = \cdots = x_i - a_i$.

We prove this by induction on $i$. The base case is trivial. Suppose $x_1 - a_1 = x_2 - a_2 = \cdots = x_i - a_i$. Since $x_i - x_j \mod 10$ is conserved and $A \rightarrow B$, $x_i - a_i \mod 10$ should be equal for all $i$. Repeat operations on $x_1, x_2, \cdots, x_{i+1}$ equal times so that $x_1$ or $x_{i+1} \leq 8$. If $x_{i+1} - a_{i+1} < x_i - a_i$, let $t = \frac{(x_i - a_i) - (x_{i+1} - a_{i+1})}{10}$. After some calculations, we can subtract 9 from all $x_j (j \neq i+1)$ $t$ times, including necessary operations subtracting 9 from $x_j (j \geq i+2)$, while not subtracting 9 from $x_{i+1}$. If $x_{i+1} - a_{i+1} > x_i - a_i$, proceed similarly.

Thus, the smallest $k$ is $8$.

### Part 2:
For the $k$ obtained in Part 1, we need to find how many tuples can be picked from $S$ such that any two distinct tuples $A, B$ satisfy $A \not\rightarrow B$.

We have practically shown that $A \rightarrow B$ is equivalent to $a_1 - b_1 \equiv a_2 - b_2 \equiv \cdots \equiv a_{10} - b_{10} \pmod{10}$. We need to count the number of tuples that cannot be derived from each other, ensuring $x_1 + x_2 + \cdots + x_{10} = 2019 \equiv 9 \pmod{10}$.

The number of such tuples is $10^8$.

The answer is: \boxed{10^8}.