No language had lexical closures in 1958. ALGOL had lexical scope, but not closures. So their part was easy. On a language level all the consequences were explored with Scheme in the 70s. Before that their were individual solutions found to create closures.

Read the history of the FUNARG problem (1970).

FP languages came up later. The first ML appeared in something like 1972/1973. I'm not sure if that had lexical closures. I doubt that. The Lisp community was one active part of the FP community that detected the problem and eventually found a solution. Scheme was the first language to demonstrate that (1975). Other FP languages also went that route (ML, where the first ML was implemented on top of Lisp, IIRC). The MacLisp branch took some time to adopt lexical closures. First a special construct was introduced to create a closure. In some other implementations the compiler was using lexical scope, but not the interpreter. Common Lisp was then in 1984 the next major Lisp dialect that settled for lexical scope (incl. closures) for both interpreted and compiled code.

The Lisp community (other than Scheme) had substantial code at the end of the 1970s, so there was some reluctance to move to lexical closures. Lexical closures also made the implementation a bit more difficult. The interpreter is simpler without them. There were also performance issues to overcome.