(Pure) Zsh, 126 bytes

zmodload zsh/datetime
s=strftime
for d ({31..9})$s -sT %A\ %dth `$s -r %F $1-$d`&&[[ $T = [^S]*$d\th ]]&&break
<<<${T/1th/1st}

Try it online!

Using the builtin strftime rather than any external programs.

zmodload zsh/datetime
# "strftime" is long enough that setting $s and using $s twice is shorter than "strftime" twice.
s=strftime   

# start at the 31st of the month, count downward
for d ({31..9})
    # Get the timestamp of "YYYY-MM-DD" with strftime -r (reverse/strptime)
    # and find "Nameofday DDth" from timestamp. (-s)ave in $T
    $s -sT %A\ %dth `$s -r %F $1-$d` &&
    # if Nameofday begins with an S or we end up on a different day of month
    # (like 02-31 converted to 03-03), keep going.
    [[ $T = [^S]*$d\th ]] && break

# Fix suffix
<<<${T/1th/1st}

zmodload zsh/datetime
# "strftime" is long enough that setting $s and using $s twice is shorter than "strftime" twice.
s=strftime   

# start at the 31st of the month, count downward
for d ({31..9})
    # Get the timestamp of "YYYY-MM-DD" with strftime -r (reverse/strptime)
    # and find "Nameofday DDth" from timestamp. (-s)ave in $T
    $s -sT %A\ %dth `$s -r %F $1-$d` &&
    # if Nameofday begins with an S or we end up on a different day of month
    # (like 02-31 converted to 03-03), keep going.
    [[ $T = [^S]*$d\th ]] && break

# Fix suffix
<<<${T/1th/1st}