address – how to evaluate if this (or any) bitcoin public key / private key combination is valid?

First, what you defining as public key and private key are actually a bitcoin address and a private key encoded in Wallet Import Format (WIF).

In order to check that the WIF and the bitcoin addresses are from the same key pair, we will need to decode the private key from its WIF format (checking that the encoding is ok), derive the public key from the private key, and generate the bitcoin address using the public key. If the generated bitcoin address matches with the provided one, then the provided one and the WIF are created from the same key pair.

In order to decode the WIF we will follow the steps from the bitcoin wiki.

Lets see how we can do this in python:

from binascii import hexlify, unhexlify
from ecdsa import SigningKey, SECP256k1
from hashlib import sha256
from bitcoin_tools.wallet import generate_btc_addr, WIF, TESTNET_WIF


def wif_to_sk(wif, network='main'):
    if network not in ['main', 'test']:
        # Add more networks if needed.
        raise Exception('Bad network')
    else:
        if network is 'main':
            version = WIF
        else:
            version = TESTNET_WIF

    decoded_wif = b58decode(wif)

    c = decoded_wif[-4:]
    v = decoded_wif[:1]

    # The byte defines the version, assert that is correct.
    assert v == chr(version)

    # The four last bytes of the WIF are the four first bytes of the checksum, check that it holds
    checksum = sha256(sha256(decoded_wif[:-4]).digest()).digest()
    assert checksum[:4] == c

    # If the private key in the WIF corresponds to a compressed public key, you must also drop the last byte, that will
    # be 01. We can check that by checking the length of the current key. 32 bytes wil mean uncompressed, while 33 and
    # a leading 01 means compressed.
    sk = hexlify(decoded_wif[1:-4])

    compressed = False

    # Notice that since we have hexlified the sk, the sizes are doubled.
    if len(sk) is 66 and sk[-2:] == '01':
        sk = unhexlify(sk[:-2])
        compressed = True
    else:
        sk = unhexlify(sk)

    return sk, compressed

# Your provided data
wif="KwfNqMip1ZdgG2o6wYQUBXv8BqkMQ8VWWeScVU5TLPZp31M5EHeq"
btc_addr="13YcHBzsBX8SxHoBftb69cXJkdXLfAVQos"
network = 'main'

sk, compressed = wif_to_sk(wif, network=network)

# Derive the public key from the private key
pk = SigningKey.from_string(sk, curve=SECP256k1).get_verifying_key()

# Assert that the computed bitcoin address and the provided one matches.
assert generate_btc_addr(pk, v=network, compressed=compressed) == btc_addr

To decode the WIF format there is a couple of things that you may know. First, the version of the network (normally either mainnet or testnet) and then, if the private key corresponds to a compressed or uncompressed public key. The version of the network will determine the first byte of the WIF format, while whether the related public key is compressed or uncompressed will determine the last byte before the checksum.

Disclaimer: The provided code uses a function generate_btc_addr, from a python library I’ve developed, that computes a bitcoin address from a given public key. Such function call a bunch of other simple functions to derive the bitcoin address, but including all on the answer will make it even longer that what it is. You can either get the library from GitHub, or get the functions from the specific file.