If you create a hardware device (by passing D3D_DRIVER_TYPE_HARDWARE when creating the device), then there will be no software emulation/fallback. The hardware will either support the feature or it won't. Windows does provide a software implementation that's called the WARP driver, but it runs everything in software and you have to specifically request it when creating your device (by passing D3D_DRIVER_TYPE_WARP). There's also the reference device which also runs in software, but it's slow beyond belief because it's intended for correctness and not performance. You also have to specifically request that, by passing D3D_DRIVER_TYPE_REFERENCE.

The simplest way to ensure compute shader functionality is to just require FEATURE_LEVEL_11_0 support from the GPU. It's easy to do this: when you call D3D11CreateDevice, just check the returned feature level (from the pFeatureLevel parameter) and then make sure that it's >= D3D_FEATURE_LEVEL_11_0. If that's the case, then you're guaranteed cs_5_0 support from the hardware. D3D_FEATURE_LEVEL_11_0 corresponds to all of the video cards that were marketed as "DX11-capable", which started with the AMD HD 5000 series and the Nvidia GTX 400 series. Technically there are FEATURE_LEVEL_10_0 and FEATURE_LEVEL_10_1 (DX10/DX10.1) video cards out there that supported the stripped down cs_4_0/cs_4_1 profiles, but support is optional and so you have to query the device at runtime to find out if you can use it (using ID3D11Device::CheckFeatureSupport and passing D3D11_FEATURE_D3D10_X_HARDWARE_OPTIONS). Honestly though cs_4_x is really limited in what it can do, and isn't really worth the effort.

Just a small addition to MJP's already great answer: you can check the available feature level without actually creating the device by passing nullptr into the device pointer. The following function is how I do this in the Hieroglyph 3 framework:

D3D_FEATURE_LEVEL RendererDX11::GetAvailableFeatureLevel( D3D_DRIVER_TYPE DriverType )
{
	D3D_FEATURE_LEVEL FeatureLevel;
	HRESULT hr;

	// If the device has already been created, simply return the feature level.
	// Otherwise perform a test with null inputs to get the returned feature level
	// without creating the device.  The application can then do whatever it needs
	// to for a given feature level.

	if ( m_pDevice ) {
		FeatureLevel = m_pDevice->GetFeatureLevel();
	} else {
		hr = D3D11CreateDevice(
			nullptr,
			DriverType,
			nullptr,
			0,
			nullptr,
			0,
			D3D11_SDK_VERSION,
			nullptr,
			&FeatureLevel,
			nullptr );

		if ( FAILED( hr ) ) {
			Log::Get().Write( L"Failed to determine the available hardware feature level!" );
		}
	}
	return( FeatureLevel );
}

That can allow you to check what feature level you have quickly and easily, and then perform some logic to determine which type and feature level of device to create.

Out of curiosity if thedifferences between shader model 4 and 5 are such that 4 is not worth the effort, why would you consider this to be the case?

To be clear I was only talking about compute shaders with shader model 4, and not shader model 4 in general. The documentation here goes into detail about the limitations of cs_4_x, but for me the main dealbreakers are the fact that you can't write to textures, and the limitations about where you can write to in thread group shared memory.