Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less
Your first approach doesn't quite work. If it is not the case that for any $k$ there is some language that requires exactly $k$ states, then all you know is that there exists a single $n$ such that every $n$-state DFA can be reduced to an equivalent DFA with fewer states.
The second approach does work, and requires a lower bound technique such as the pumping lemma (the pumping constant is the number of states) or Myhill–Nerode theory. Try the following language: all words whose length is a multiple of $k$.