Would x86 still be fully programmable if it didn't have the Sign Flag (SF)?

You don't even need any flags because in x86 MOV is already Turing-complete and there's a compiler that can compile C code into an executable with only MOVs (or only one of XOR, SUB, ADD, XADD, ADC, SBB, AND/OR, PUSH/POP, 1-bit shifts, or CMPXCHG/XCHG)

If you have bitwise operations then the sign bit can be easily obtained with AND or right shift

Yes, x86 would still be Turing-complete without SF, and even fairly efficiently programmable. Signed-integer compares (other than == / !=) would be slower, but still doable. So x86-without-SF is still much more efficient than one-instruction-computing hacks like using only MOV (with lots of lookup tables and addressing modes). You can still do normal add / subtract / multiply with the normal instructions, and just emulate the signed-compare conditions that involve SF.

For example, you could emulate cmp eax, ecx/jl using two temporary registers. jl jumps if SF != OF. (There are probably easier ways to do this emulation, but this most directly demonstrates that you can get the MSB of a result into a flag other than SF, and thus could emulate it in other cases.)

; inputs: EAX and ECX
; clobbers: EDX and EAX
;;; jumps if EAX < ECX,  like cmp eax,ecx / jl

    mov  edx, eax
    sub  edx, ecx        ; sets OF, and would set SF it it existed
    bt   edx, 31         ; CF = MSB, other flags unmodified.
 ;; jump if CF != OF    , like jl = SF!=OF in normal x86
    pushf
    pop  eax
    and  eax, 0x0801     ; isolate CF and OF
    or   al, ah          ; combine both into the low byte, setting FLAGS
    jpo  eax_lower       ; jump if parity odd: CF != OF means only one bit is set

(EFLAGS bit positions)

Note that PF, the parity flag, is only set according to the low byte of the result; after just the AND, it could only tell you about CF, bit 0 of EFLAGS. It's an unfortunate design decision that OF is outside the low byte of FLAGS, otherwise lahf could replace pushf/pop reg.

This is just the first idea that occurred to me, I'm sure it could be done more efficiently. (But a lot of code would favour unsigned numbers so compares can be fully efficient.)

If you had to avoid 386 BT for setting just CF without messing up other bits, you could of course just shr dx, 15 to bring the MSB down to the bottom, or rol dx, 1. (But that writes FLAGS, so you'd do it after pushf/pop reg, and maybe you'd choose your shift or rotate count to line it up with OF.)

Some 8-bit ISAs I think didn't have signed compare conditions, and people still managed to get some stuff done on them. :P

Yes, in fact, that's the way MIPS works.  MIPS has no flags, no sign flag, no overflow flag, no zero flag, etc..  It has instructions that will test a register for zero/non-zero, for <= or > 0.