The consensus blockchain doesn't contain any easily queryable information to figure out the creation time of a contract based solely on its address. If you have the hash of the transaction that created the contract, retrieving that would give you back the block number too.
If you need only to occasionally figure out the creation block of a/some contracts, you could also consult a block explorer for the first transaction.
However, although finding events belonging to a contract in the entire chain is obviously slower than searching from only a known starting block, event queries use mip-mapped bloom filters, so they should be relatively fast at the current chain size. The canonical solution is to create a filter from block 0 initially, and then store away the block number until which you already processed the blocks and only continue from there the next time.