Сократ противопоставлял себя софистам. Софисты брали деньги за обучение "мудрости" и утверждали, что владеют истинным знанием. Сократ считал это самообманом.
Суть фразы: признание границ собственного понимания открывает путь к настоящему познанию. Человек, который уверен что все знает, перестает искать. Сократ говорил, что он мудрее других не потому что знает больше, а потому что осознает свое незнание, тогда как другие не осознают.
Кстати, в оригинале у Платона ("Апология Сократа", 21d) фраза звучит немного иначе. Сократ рассказывает, как ходил к политикам, поэтам и ремесленникам, чтобы проверить слова дельфийского оракула о том, что нет никого мудрее Сократа. И каждый раз обнаруживал одно и то же: эти люди считали себя знающими, но при расспросах оказывалось, что их знание поверхностно или ограничено узкой областью. Сократ же хотя бы понимал, что его знание тоже ограничено.
Насчет парадокса. Формально да, "знать, что не знаешь" - это уже знание. Но Сократ оперировал разными уровнями: знание-о-мире (факты, истины) и знание-о-себе (рефлексия). Он не утверждал абсолютное незнание. Он утверждал, что у него нет надежного, окончательного знания о природе вещей, добродетели, справедливости. И этот зазор между "я думаю что знаю" и "я действительно знаю" - центральная тема всей сократовской философии.