In this context, the phrase "use all means necessary and appropriate" should be viewed as a single phrase rather than words in isolation, and it essentially simply confers discretion on the President to decide what is necessary and appropriate, rather than being a limiting direction.
The word "appropriate" is included in the phrase to avoid a crabbed construction of the word "necessary" to mean "only if absolutely necessary", and to instead mean "related to carrying out the objective" even if the means chosen are not actually the only way that the objective could be accomplished.
It is a close relative of the constitutional grant to Congress under Article I, Section 8 of the U.S. Constitution to enact legislation "necessary and proper" to carry out the enumerated powers of Congress set forth in that section, and has a very similar meaning.
Taken as a whole, the primary limitation imposed by "necessary and appropriate" it to prohibit the President from using this statute as a grant of authority to do something completely unrelated to getting someone out of International Criminal Court custody (e.g. providing disaster relief to fire victims in California, or ignoring an environmental regulation in connection with building a border wall with Canada).