DeanOC's helpful answer provides an effective solution.
As for why the parentheses (brackets) are needed:
PowerShell has two fundamental parsing modes:
argument mode, which works like traditional shells
expression mode, which works like traditional programming languages.
Running Get-help about_Parsing provides an introduction to these modes.
Test-Path $path1 and Test-Path $path2 in isolation are parsed in argument mode.
Operator -and can only be used in expression mode.
In order to use the output of the argument-mode Test-Path commands in expression mode, they must be enclosed in (...):
Use of (...) forces a new parsing context, and
the 1st token of a given parsing context determines whether it is parsed in argument or expression mode.
Another thing to consider is PowerShell's pervasive support for collections, which often allows you to operate at a higher level of abstraction:
$paths = "C:\Windows", "C:\Users" # define *array* of input paths
if ((Test-Path $paths) -notcontains $False) { # See if ALL paths exist.
"ALL paths exist."
}
Test-Path accepts an array of paths to test, and outputs a corresponding array of Booleans indicating the respective existence.
Operator -notcontains tests non-membership in the LHS array; in other words: if no Boolean returned by Test-Path is $False, the implication is that all input paths exist.
Note that Write-Host was deliberately omitted, because in order to send something to PowerShell's success stream (the analog to stdout in traditional shells), you don't need an explicit output command at all, and, conversely, Write-Host actually bypasses the success stream - see this blog post.